Ulam sequence
The Ulam sequence is an interesting mathematical sequence of integers. It starts with [1 2]
. At each step, the next element is:
- not already in the sequence
- a sum of two previous elements
- the number must be produced by only one sum
- the smallest in case there are multiple candidates
Let's walk through an example.
As we said before, the first two elements are 1
and 2
. Those sum to 3
, and there's only one way to get it, so 3
is the next element.
[1 2 3]
Now, there are 3 possible sums: 1+2=3
, 1+3=4
, and 2+3=5
. 3
already exists, so it's out. 4
and 5
both only have one way to produce them, but 4
is smaller, so it's the next element.
[1 2 3 4]
Now: 1+2=3
(done), 1+3=4
(done), 1+4=5
, 2+3=5
, 2+4=6
, 3+4=7
. 5
is produced two ways, so it's out. 6
<7
, so the next element is 6
.
[1 2 3 4 6]
Your task is to create a lazy Ulam sequence.
Example
(take 2 (ulam)) ;=> (1 2)
(take 5 (ulam)) ;=> (1 2 3 4 6)
(take 17 (ulam)) ;=> (1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53)
Thanks to this site for the problem idea, where it is rated Expert in Java. The problem has been modified.
Please submit your solutions as comments on this gist.
To subscribe: https://purelyfunctional.tv/newsletter/
This was a fun exercise - I made many edits, ending with two side-by-side variations of the basic algorithm,
which looks at those existing Ulam numbers below half of the current candidate value, mentioned in this paper.
One variation is a hand-rolled lazy-sequence using a recursive function taking the state,
cons
ing the computed value from it,and feeding it to the next call). The other one uses
iterate
and a transducing(map first)
.In both cases the approach is to pick a candidate
c
(c0 = U(n) + 1
) , then go through each numberU(k)
in theUlam sequence search space in descending order, and test that
diff(c,k) = c - U(k)
is also in the sequence:U(j)
, j < k yields a memberdiff(c,j)
then c is a comfirmed Ulam number;To quickly extract the bottom portion of the existing sequence as the search space argument to
next-ulam
I tried two implementatons of a fast binary-search function (big-O(logN)): one hand-rolled and the other using
java.util.Collections.binarySearch (
bin-search
,bin-search2
resp.).Surprisingly, the bench tests show that the hand-rolled versions (ulam and bin-search) perform slightly better,
especially bin-search which I expected the java version to be much faster.