turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

Find a Community

- Home
- /
- SAS Programming
- /
- Base SAS Programming
- /
- Project Euler SAS solution

Topic Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

08-19-2016 12:49 AM

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

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to LaurieF

08-19-2016 02:34 AM

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

---------------------------------------------------------------------------------------------

Maxims of Maximally Efficient SAS Programmers

Maxims of Maximally Efficient SAS Programmers

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to LaurieF

08-19-2016 04:19 AM

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.

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to Ksharp

08-19-2016 09:17 PM

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.

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to LaurieF

08-19-2016 10:38 PM

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 .