We’re smarter together. Learn from this collection of community knowledge and add your expertise.

Project Euler solution in SAS: Number of shared divisors

by Super Contributor on ‎10-31-2016 02:29 PM (998 Views)

As many will attest, my mathematical abilities aren't great. My instincts aren't bad, but when I have to go beyond the delights of ones and zeroes, I'm prone to make mistakes.

 

About six months ago I started hacking my way through https://projecteuler.net. I got stuck at about problem 30, and pretty much gave up. I was coding up the solutions in Apple's Swift - actually the reason was to teach myself to be a better Swift programmer.

 

A couple of days ago I thought I'd have another go, and happened across problem 179 (https://projecteuler.net/problem=179), which reads:

Find the number of integers 1 < n < 107, for which n and n + 1 have the same number of positive divisors. For example, 14 has the positive divisors 1, 2, 7, 14 while 15 has 1, 3, 5, 15.

 

I wrote a solution which was taking ages (I gave up after thirty minutes), then I thought about it, recoded it and it came down to nine seconds.

 

While I was out walking the dog today, I thought about writing it in SAS. When I came home I fired up SAS Studio on my Mac (I love being able to do that!) and hacked out the following code, using a hash table and 'by - notsorted'. The hash population takes 2'31", but the analysis steams through in four seconds.

 

I'm ridiculously proud of: count + not(last.divisors);

 

data _null_;
	length i 8;
	length divisors 4;
	max=1e7;
	dcl hash divhash(hashexp: log2(max), ordered: 'a');
	divhash.definekey('i');
	divhash.definedata('i', 'divisors');
	divhash.definedone();
	i=1;
	divisors=1;
	divhash.add();

	do i=2 to max;
		divisors=2;       /* All numbers > 1 have two divisors */
		rc=divhash.add();
	end;

	do j=2 to int(max / 2);
		do i=j * 2 to max by j;
			rc=divhash.find();
			divisors + 1;
			rc=divhash.replace();
		end;
	end;
	divhash.output(dataset: 'divisors');
	stop;
run;

data _null_;
	set divisors nobs=max end=eof;
	by divisors notsorted;
	retain count 0;
	format max count comma14.;
	count + not(last.divisors);

	if eof;
	put 'There are ' count +(-1) ' consecutive positive divisors between 1 and ' 
		max +(-1) '.';
run;

There are always so many ways to skin a cat. I could have done it in one step by setting up an array instead of the hash. But I wanted to take advantage of by-group processing.

 

You know the old criticism of "some people have too much time on their hands"? Sometimes I like being "some people".

 

The straight programming style (not SAS-specific) was much more efficient: 5.59 seconds.

 

 

%let max = 10000000;

data _null_;
	length i 8;
	max=&max;
	array divisors[&max] 4 _temporary_;
	divisors[1]=1;

	do i=2 to max;
		divisors[i]=2;
	end;

	do j=2 to int(dim(divisors) / 2);
		do i=j * 2 to max by j;
			divisors[i] + 1;
		end;
	end;
	
	count = 0;
	do i = 2 to dim(divisors) - 1;
	   count + divisors[i] = divisors[i + 1];
	   end;
	format max count comma14.;
	put 'There are ' count +(-1) ' consecutive positive divisors between 1 and ' 
		max +(-1) '.';
    stop;   
run;

 

 

But not as much fun.

Contributors
Your turn
Sign In!

Want to write an article? Sign in with your profile.


Looking for the Ask the Expert series? Find it in its new home: communities.sas.com/askexpert.