topic Re: Project Euler SAS solution in SAS Programming

Project Euler SAS solution

LaurieF — Fri, 19 Aug 2016 04:49:44 GMT

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".

Re: Project Euler SAS solution

Kurt_Bremser — Fri, 19 Aug 2016 06:34:20 GMT

@LaurieF wrote:

.............

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

If it wasn't for that, I'd probably not be posting here 😉

Re: Project Euler SAS solution

Ksharp — Fri, 19 Aug 2016 08:19:36 GMT

Ha. You should forward this url to @Rick_SAS . I bet he gonna love it . If you want fast algorithm , I think you should pick up all the prime number in it firstly.

Re: Project Euler SAS solution

LaurieF — Sat, 20 Aug 2016 01:17:03 GMT

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.

Re: Project Euler SAS solution

Ksharp — Sat, 20 Aug 2016 02:38:06 GMT

Sorry. Forget what I said, I totally have no idea about it.
Your algorithm is amazing . I don't how it work .
I love that URL .