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