19
\$\begingroup\$

Given an integer n (where n < 10001) as input, write a program that will output the first n Ulam numbers. An Ulam number is defined as follows:

  1. U1 = 1, U2 = 2.
  2. For n > 2, Un is the smallest integer which is greater than Un-1 that is the sum of two distinct earlier terms in exactly one way.

For example, U3 is 3 (2+1), U4 is 4 (3+1) (note that (2+2) does not count as the terms are not distinct), and U5 is 6, (U5 is not 5 because 5 can be represented as either 2+3 or 4+1). Here are the first few Ulam numbers:

1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99

This is code golf, so the shortest entry wins.

\$\endgroup\$
  • \$\begingroup\$ Does the output have to be as shown (list separated by comma and space) or can we output e.g., an array? \$\endgroup\$ – Dennis Sep 8 '14 at 1:54
  • \$\begingroup\$ What's the minimum value of n we have to handle? \$\endgroup\$ – Dennis Sep 8 '14 at 2:06
  • 1
    \$\begingroup\$ @Dennis Space or comma or both is fine. Minimum value of n is 1. \$\endgroup\$ – absinthe Sep 8 '14 at 2:10
  • \$\begingroup\$ As it is, I have brackets around my list. Is that OK too or should I remove them? \$\endgroup\$ – Dennis Sep 8 '14 at 2:12
  • 1
    \$\begingroup\$ @Dennis Brackets are fine. \$\endgroup\$ – absinthe Sep 8 '14 at 2:12

20 Answers 20

9
\$\begingroup\$

CJam, 47 41 37 bytes

li4,1${__m*{_~<\:+*}%$2/z:^$2=+}*1><`

Try it online.

Example run

$ cjam <(echo 'li4,1${__m*{_~<\:+*}%$2/z:^$2=+}*1><`') <<< 26
[1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69 72 77 82 87 97 99]

How it works

This basic idea is the following:

  1. Start with the array A := [ 0 U₁ U₂ ... Uₖ ].

  2. Compute S, the array of all sums x + y such that x,y ∊ A and x < y.

  3. Discard all non-unique sums from S. Since every Ulam number greater than 2 is both the sum of two smaller ones and the sum of zero and itself, this discards the Ulam numbers U₃, U₄, ... Uₖ.

  4. The remaining array is [ U₁ U₂ Uₖ₊₁ ... ], so the next Ulam number is the third smallest element. Append it to A and go back to step 1.

li                                    " Read one integer (I) from STDIN.                  ";
  4,                                  " Push the array A = [ 0 1 2 3 ].                   ";
    1${                        }*     " Do the following I times:                         ";
       __m*                           " Push the Cartesian product A × A.                 ";
           {       }%                 " For each pair (x,y) in A × A:                     ";
            _~<\:+*                   " Compute (x + y) * (x < y).                        ";
                     $2               " Sort the resulting array.                         ";
                       /              " Split it into chunks of length 2.                 ";
                        z             " Transpose the resulting two-dimensional array.    ";
                         :^           " Compute the symmetric difference of its rows.     ";
                           $          " Sort the resulting array.                         ";
                            2=        " Extract its third element.                        ";
                              +       " Push it on the array A.                           ";
                                 1>   " Discard the first element of A (0).               ";
                                   <  " Discard all but the first I elements of A.        ";
                                    ` " Push a string representation of A.                ";
\$\endgroup\$
  • \$\begingroup\$ An input of 100 already takes several seconds. I suppose computing the maximum input 1e5 would take ages? \$\endgroup\$ – Martin Ender Sep 8 '14 at 9:23
  • \$\begingroup\$ @MartinBüttner: The Java interpreter is a lot faster, but it's still slow. All brute-force algorithms are O(n²) or worse. Using a stack-oriented language for arrays is never pretty (e.g., computing an arrays length requires copying the entire array), so actual execution time is probably O(n³). \$\endgroup\$ – Dennis Sep 8 '14 at 13:01
  • 1
    \$\begingroup\$ @MartinBüttner: WolframAlpha, so 1e4 (thankfully, not 1e5) should take less than three weeks. \$\endgroup\$ – Dennis Sep 8 '14 at 13:15
6
\$\begingroup\$

J - 46 char

Function taking n as argument.

_2}.(,]<./@-.~</~({.+_*1<#)/.~@#&,+/~)@[&0&1 2

Explained by explosion:

    (                                )          NB. procedure for a list:
                                  +/~           NB.   take an addition table
              </~              #&,              NB.   select the top right half (no diag)
                 (        )/.~@                 NB.   for each unique value:
                       1<#                      NB.     if more than one present
                  {.+_*                         NB.     add infinity to it
      ]    -.~                                  NB.   remove existing Ulam numbers
       <./@                                     NB.   take the smallest
     ,                                          NB.   append to Ulam numbers
                                      @[&0      NB. repeat this procedure:
                                          &1 2  NB.   n times starting with [1, 2]
_2}.                                            NB. drop the last two numbers
\$\endgroup\$
  • \$\begingroup\$ There's +_*... \$\endgroup\$ – tomsmeding Sep 9 '14 at 20:23
6
\$\begingroup\$

T-SQL, 301 300 288 287

I've committed a little light SQL abuse.

DECLARE @N INT=100,@T INT=1DECLARE @ TABLE(I INT,U INT)INSERT @ VALUES(1,1),(2,2)#:IF @T>2INSERT @ SELECT TOP 1@T,A.U+B.U FROM @ A,@ B WHERE A.U>B.U GROUP BY A.U+B.U HAVING COUNT(*)=1AND A.U+B.U>ALL(SELECT U FROM @)ORDER BY 2SET @T+=1IF @T<=@N GOTO # SELECT U FROM @ WHERE I<=@N ORDER BY I

Try it in SQL Server 2008 here.

@N holds the input integer. Change the example "100" to what n should be. "10000" will probably finish eventually, but I haven't let that run to completion. This entry's char count is for a one-digit input. Output is in query result form.

\$\endgroup\$
5
\$\begingroup\$

Haskell, 70 67 characters

u n=take n$1:2:[x|x<-[1..],[_]<-[[y|y<-u$n-1,z<-u$n-1,y<z,y+z==x]]]

usage:

>u 6
[1,2,3,4,6,8]
\$\endgroup\$
5
\$\begingroup\$

GolfScript (41 37 bytes)

~.14*,3,\{1$.{2$1$-.@<*}%&,2=*|}/0-<`

Online demo

Cartesian products in GolfScript are quite long, so this takes a different approach. The long-term growth of the Ulam numbers is that the nth Ulam number is about 13.5n, but in the first 10000 terms the greatest ratio between the nth Ulam number and n is just under 13.3. So given n we can filter the first 14n numbers to find those which belong in the sequence.

With thanks to Dennis for 41->37.

\$\endgroup\$
  • 1
    \$\begingroup\$ This is quite fast. n = 1000 takes under a minute with GolfScript; a port to CJam completes n = 1000 in 8 seconds and n = 10000 in 1h 20 m. -- You can save four bytes by combining your approach with mine, namely including 0 in the array and discarding it afterwards. That allows using set union instead of the block and eliminates the need for a variable: ~.14*,4,\{1$.{2$1$-.@<*}%&,2=*|}/1><` \$\endgroup\$ – Dennis Sep 8 '14 at 15:47
  • \$\begingroup\$ @Dennis, how many chars shorter is the CJam? I assume that none of the operations get longer, and I'm pretty sure it has a one-char alias for 14. \$\endgroup\$ – Peter Taylor Sep 8 '14 at 18:01
  • \$\begingroup\$ Yes, 14 is just E. But you need to read from STDIN, convert the integer to a singleton before performing set union (I'll file a bug report about that) and 2$ won't work in the inner loop since CJam modifies the stack after each iteration... I've tried several different tricks, but the shortest one was exactly 37 bytes: li4,1$E*{__{I1$-_@<*}%&,2=I*a|}fI1><` \$\endgroup\$ – Dennis Sep 8 '14 at 18:16
5
\$\begingroup\$

JavaScript ES6, 100 ... 93 90 characters

Run this in Web Console or Scratchpad of latest Firefox (Nightly or release).

EDIT 8 Golfed a lot!!! and made it down to 94 characters 93 90 characters (thanks to @openorclose). (My first sub 100)

Here is my version which is much faster but is 3 characters longer (107 characters) and is exactly the same amount of characters as above and is much smaller than the brute force method below!, (thanks to edc65 ) :

u=n=>(s=>{for(r=[i=l=1];c=l<n;i+=c&&i-2?1:s[r[l++]=i]=1)r.map(j=>c-=j<i/2&s[i-j])})([])||r

I will keep trying to golf it further. But we are squeezing it out of the scope of JS :P

Here are some numbers when I run this inside a script tag in a webpage:

n           time (s)
10            0.001
100           0.005
1000          2.021
10000       236.983
100000      pending tldr; Too long didn't run :P

This is my first submission which is heavily inspired by @rink.attendant.6's answer in JavaScript.

u=n=>{for(l=[1,g=2],i=3;g<n;++i){z=1;for(j of l)for(k of l)z-=j<k&j+k==i;!z?l[g++]=i:0}return n>1?l:[1]}

I know this can be golfed even further. I will post a non-bruteforced solution too, which might be even shorter.

EDIT 1: Golfed a bit more and fixed for n = 1

I must say that I do envy Haskell and J for such super handy shortcuts for every kind of requirement -_-

\$\endgroup\$
  • \$\begingroup\$ about Haskell, i think the functional style and the syntax make most the difference (for example, no hideous giant loops), although the amount of functions is always nice :-) \$\endgroup\$ – proud haskeller Sep 8 '14 at 12:46
  • 1
    \$\begingroup\$ The faster one can surely be golfed more: (104) u=n=>{for(s=[,1,1],r=[i=1,l=2];c=l<n;!c?s[r[l++]=i]=1:0,i++)for(j of r)c-=j<i/2&s[i-j];return n>1?r:[1]} and maybe even more \$\endgroup\$ – edc65 Sep 8 '14 at 21:27
  • 1
    \$\begingroup\$ 1. I still barely understand how you avoided the double loop.Kudos 2.Golf tip:in E6 I always try to avoid return. 100:u=n=>(s=>{for(r=[i=1,l=2];c=l<n;i+=!c?s[r[l++]=i]=1:1)for(j of r)c-=j<i/2&s[i-j]})([,1,1])|n>1?r:[1] \$\endgroup\$ – edc65 Sep 8 '14 at 22:02
  • 1
    \$\begingroup\$ There one less char: u=n=>(s=>{for(r=[i=l=1];c=l<n;i+=c&&i-2?1:s[r[l++]=i]=1)for(j of r)c-=j<i/2&s[i-j]})([,1])||r \$\endgroup\$ – openorclose Sep 10 '14 at 13:58
  • 1
    \$\begingroup\$ 90 chars: u=n=>(s=>{for(r=[i=l=1];c=l<n;i+=c&&i-2?1:s[r[l++]=i]=1)r.map(j=>c-=j<i/2&s[i-j])})([])||r Unless the [,1] is needed somewhere \$\endgroup\$ – openorclose Sep 11 '14 at 1:09
5
\$\begingroup\$

Perl - 71 bytes

#!perl -p
@a=$b[2]=1;1while$b[++$a]^1||$_>map(++$b[$_+$a],@a)&&push@a,$a;$_="@a"

Try it online!

Counting the shebang as one.
Using a second array to store the sums seems to be significantly faster than a hash. Memory usage is also less, which I wouldn't have expected.

Sample usage:

$ echo 30 | perl ulam.pl

Sample output:

1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69 72 77 82 87 97 99 102 106 114 126

Approximate runtimes:

n = 100     0.015s
n = 1000    0.062s
n = 10000   4.828s
\$\endgroup\$
  • 2
    \$\begingroup\$ 8.6 s for n == 1e4. Amazing! The output for n == 1 is incorrect though; it should print a single number. \$\endgroup\$ – Dennis Sep 8 '14 at 13:05
  • \$\begingroup\$ @Dennis now fixed. \$\endgroup\$ – primo Sep 8 '14 at 13:40
4
\$\begingroup\$

Java, 259

import java.util.*;class C{public static void main(String[]a){List<Integer>l=new ArrayList<>();l.add(1);l.add(2);for(int i=3,z=0;l.size()<new Long(a[0]);i++,z=0){for(int j:l){for(int k:l){if(j<k&j+k==i)z++;}}if(z==1)l.add(i);}l.forEach(System.out::println);}}

Brute force works well for this.

import java.util.*;
class C {
    public static void main(String[] a) {
        List<Integer>l = new ArrayList<>();
        l.add(1);
        l.add(2);
        for (int i = 3, z = 0; l.size() < new Long(a[0]); i++, z = 0) {
            for (int j : l) {
                for (int k : l) {
                    if (j < k & j + k == i)
                        z++;
                }
            }
            if (z == 1)
                l.add(i);
        }
        l.forEach(System.out::println);
    }
}
\$\endgroup\$
  • \$\begingroup\$ 1. Printing the result seems to require Java 8, which might be worth mentioning. 2. The output for 1 should be a single number. \$\endgroup\$ – Dennis Sep 8 '14 at 5:59
  • 1
    \$\begingroup\$ Does this handle an input of 10k? \$\endgroup\$ – Martin Ender Sep 8 '14 at 9:28
  • \$\begingroup\$ I believe the j and k for loops don't need braces. \$\endgroup\$ – Michael Easter Sep 10 '14 at 4:33
  • \$\begingroup\$ As Martin implies, I too would like to see a timed execution of this program for N = 10K . \$\endgroup\$ – Michael Easter Sep 10 '14 at 14:02
4
+200
\$\begingroup\$

APL (Dyalog Extended), 36 35 bytes

-1 byte by Adám

{⍵↑{⍵,⊃∧(∊⊢⊆⍨⍧⍨∊2 3⍨)⍵~⍨,+⍀⍨⍵}⍣⍵⍳2}

Try it online!

{⍵↑{⍵,⊃∧(∊⊢⊆⍨⍧⍨∊2 3⍨)⍵~⍨,+⍀⍨⍵}⍣⍵⍳2}      Monadic function taking an argument n:

{⍵,⊃∧(∊⊢⊆⍨⍧⍨∊2 3⍨)⍵~⍨,+⍀⍨⍵}   Helper function to compute the next Ulam number
                                    given ⍵ (the first few Ulam numbers)
                        +⍀⍨⍵      Make an addition table from ⍵.
                       ,          Flatten into a list.
                   ⍵~⍨            Remove all entries already in ⍵.

     (∊⊢⊆⍨2 3∊⍨⍧⍨)               Helper function taking an argument x:
                ⍧⍨                  The count of elts of x in itself                 
           2 3∊⍨                    1s where those counts are in (2 3), else 0s.*
       ⊢⊆⍨                          Partition x, removing values corresponding to 0s.
      ∊                             Join the partitions into a single list.

    (∊⊢⊆⍨⍧⍨∊2 3⍨)                Keep all elements that occur exactly 2 or 3 times.
                                  (i.e. that occur once as a
                                  sum of distinct elements of ⍵).
    ∧                         Sort ascending.
   ⊃                          Take the first value (the next Ulam #).
 ⍵,                           Append that value to ⍵.

{⍵↑{...}⍣⍵⍳2}
{  {...}⍣⍵  }                 Call the helper function n times
           ⍳2                 starting with (1 2). First n+2 Ulam numbers.
 ⍵↑                           Keep the first n elements.

When we make the addition table, diagonal elements are twice the entries in ⍵. Non-diagonal elements are sums of distinct elements, with each \$x\$ occurring twice for each way \$x\$ can be written as a sum of distinct elements. Therefore, each number \$x\$ occurs \$2a+b\$ times, where \$a\$ is the number of ways \$x\$ can be written as a sum of distinct elements from ⍵, and \$b\$ is 1 iff \$x\$ is twice some entry in ⍵. We want \$a=1\$, so it is sufficient to check \$2a+b \in \{ 2, 3\}\$.

* (In ngn/APL, a constant can end a train without using . But ngn/APL doesn't have count-in, so we need ⍨ somewhere.)

\$\endgroup\$
  • \$\begingroup\$ {(2 3∊⍨⍵⍧⍵)/⍵}(∊⊢⊆⍨⍧⍨∊2 3⍨) \$\endgroup\$ – Adám Feb 11 at 10:37
3
\$\begingroup\$

PHP 5.4+, 164

Same approach as my answers:

<?function u($n){for($l=[1,2],$i=3;count($l)<$n;++$i){$z=0;foreach($l as $j){foreach($l as $k){$z+=$j<$k&$j+$k==$i;}}if($z==1)$l[]=$i;}return array_slice($l,0,$n);}
\$\endgroup\$
2
\$\begingroup\$

CoffeeScript, 119 114

Lately I've been practising CoffeeScript to improve at golfing JavaScript, so here's my JavaScript answer compiled into CoffeeScript:

u=(n)->l=[1,2];i=3;z=0;(for j in l
 for k in l
  z+=j<k&j+k==i
l.push(i) if z==1;++i;z=0)while l.length<n;l[..n-1]

I don't understand loops and comprehensions in CoffeeScript very well so perhaps this can be golfed further but it's what I have for now. Newlines are counted as one character (Unix style).

\$\endgroup\$
2
\$\begingroup\$

JavaScript, 147 154 150 (136)

Heavily inspired by @Ypnypn's brute-force Java solution posted earlier:

function u(n){for(l=[1,2],i=3;l.length<n;++i){z=0;l.forEach(function(j){l.forEach(function(k){z+=j<k&j+k==i})});if(z==1)l.push(i)}return l.slice(0,n)}

Thanks for @Dennis for shaving 4 to 18 bytes off my original version

Dangerous version (using for..in loops)

I would not recommend running this because looping through an object that is an instanceof Array using a for..in loop could cause your machine to burst into flames and/or transform into an angry killing machine, but here it is:

function u(n){for(l=[1,2],i=3;l.length<n;++i){z=0;for(j in l)for(k in l)z+=l[j]<l[k]&l[j]+l[k]==i;if(z==1)l.push(i)}return l.slice(0,n)}

Ungolfed

function u(n) {
    var l = [1, 2],
        i = 3,
        j, k, z;

    for (; l.length < n; ++i) {
        z = 0; 
        l.forEach(function (j) {
            l.forEach(function (k) {
                if (j < k & j + k === i) {
                    z++;
                }
            });
        });
        if (z === 1) {
            l.push(i);
        }
    }

    return l.slice(0, n);
}
\$\endgroup\$
  • \$\begingroup\$ The output for 1 should be a singleton. \$\endgroup\$ – Dennis Sep 8 '14 at 6:00
  • \$\begingroup\$ @Dennis Thanks, corrected. \$\endgroup\$ – rink.attendant.6 Sep 8 '14 at 6:06
  • \$\begingroup\$ 1. If you move z=0 inside the loop, you need it only once. 2. for(j in l)for(k in l)z+=l[j]<l[k]&l[j]+l[k]==i; is a lot shorter than the l.forEach approach. \$\endgroup\$ – Dennis Sep 8 '14 at 6:15
2
\$\begingroup\$

Mathematica, 107 91 bytes

Nest[#~Append~Min@Cases[Tally[Tr/@#~Subsets~2],{n_,1}:>n]&,{1,2},i=Input[]]~Drop~{3}~Take~i

It's a very direct implementation of the spec.

  • Find all pairs.
  • Delete all duplicates.
  • Delete all numbers less than the last Ulam number.
  • Append the minimum to the list.

I'm also applying Dennis's trick of including sums with 0, but the catch is that this makes the third element of the list 0 before resuming as one would expect, so I need to remove that element from the list.

It handles an input of 1000 in a few seconds, but I doubt that you'll get a result for 10k in a reasonable amount of time. But I don't think any of the others performs well on that either.

\$\endgroup\$
2
\$\begingroup\$

OCaml - 254 Characters

The code use an hash table to store the sum of the current elements of the list and update it each time a new element is computed.

open Hashtbl let h=create 7 let()=add h 3 1 let rec r n i l=if n=0then List.rev l else if mem h i&&find h i=1then(List.iter(fun x->if mem h(x+i)then replace h(x+i)2else add h(x+i)1)l;r(n-1)(i+1)(i::l))else r n(i+1)l let u n=if n=1then[1]else r(n-2)3[2;1]

Usage:

Within OCaml interpreter:

# u 26;;
- : int list =
[1; 2; 3; 4; 6; 8; 11; 13; 16; 18; 26; 28; 36; 38; 47; 48; 53; 57; 62; 69;
 72; 77; 82; 87; 97; 99]

Ungolfed

open Hashtbl
let h = create 7
let() = add h 3 1
let rec r n i l =
  if n=0 then List.rev l
  else if mem h i && find h i=1 then
    begin
      List.iter
        (fun x-> if mem h(x+i) then replace h (x+i) 2 else add h (x+i) 1)
        l;
      r (n-1) (i+1) (i::l)
    end
  else r n (i+1) l

let u n = if n=1 then [1] else r (n-2) 3 [2;1]
\$\endgroup\$
2
\$\begingroup\$

Python, 137 128 126 characters.

U,i=[1,2],2
for _ in [[0]]*(input()-2):
 t=_*3*i
 for a in U:
  for b in U:t[a+b]+=a!=b
 i=t[i+1:].index(2)+i+1;U+=[i]
print U

This is my first golf, and I've brought it down from ~250 characters, I'm pretty happy but would love suggestions on how to improve!

\$\endgroup\$
  • \$\begingroup\$ Minor, but worthwhile: combine lines 5&6 to for b in U:t[a+b]+=a!=b and lines 8&9 to while t[i]-2:i+=1 \$\endgroup\$ – James Waldby - jwpat7 Sep 10 '14 at 4:51
  • \$\begingroup\$ Thanks for the suggestion! I also changed the while loop to an index but it didn't save as many characters as I was expecting. \$\endgroup\$ – QuadmasterXLII Sep 10 '14 at 14:14
  • \$\begingroup\$ 2 more chars: init U to [1], and move line 7 to after the for \$\endgroup\$ – James Waldby - jwpat7 Sep 10 '14 at 14:55
  • \$\begingroup\$ You can still get rid of 2 chars by changing U,i=[1,2],2 to U,i=[1],2 and input()-2 to input()-1 and t=_*3*i to t=_*3*i;U+=[i] and remove ;U+=[i] at end of for \$\endgroup\$ – James Waldby - jwpat7 Sep 11 '14 at 18:18
2
\$\begingroup\$

Jelly, 20 bytes

Œc§ḟµḟœ-Q$Ṃɓ;
2RÇ⁸¡ḣ

Try it online!

Œc§ḟµḟœ-Q$Ṃɓ;    Helper link that appends the next number to x, a list of Ulam numbers:
Œc                  All unordered pairs of x
  §                 Sum each pair
   ḟ                Filter out the numbers already present in x.
    µ               Let this list be y. Then apply the following chain:

     œ-Q$Ṃ          Find the minimum of all unique elements.
     ḟ                Take y and filter out the elements in
      œ-Q$            the multiset difference between y and its unique elements.
          Ṃ           Then find the Ṃinimum of the result.

           ɓ;    Append (ɓ reverses argument order) the result to 


2RÇ⁸¡ḣ           Main link:
2R               Start with [1,2].
  Ç⁸¡            Apply the helper link (Ç) n (⁸) times to generate n+2 Ulam #s.
     ḣ           Keep the first n values.
\$\endgroup\$
0
\$\begingroup\$

C#, 257

Brute force approach, using LINQ:

using System.Linq;class U{void F(int n){var u=n<2?new int[]{1}:new int[]{1,2};for(int i=3;u.Length<n;++i)if(u.SelectMany(x=>u,(a,b)=>new{A=a,B=b}).Count(x=>x.A>x.B&&x.A==i-x.B)==1)u=u.Union(new int[]{i}).ToArray();System.Console.Write(string.Join("",u));}}

Ungolfed, With Test Harness

using System.Linq;
class Ulam
{
    void F(int n)
    {
        //handle special case where n = 1 (ugh)
        var u = n < 2 ? new int[] { 1 } : new int[] { 1, 2 };
        for (int i=3; u.Length<n; ++i)
            if (u.SelectMany(x => u, (a, b) => new { A = a, B = b })
                     .Count(x => x.A > x.B && x.A == i - x.B) == 1)
                u = u.Union(new int[] { i }).ToArray();
        System.Console.Write(string.Join(" ",u));
    }
    public static void Main(string[] args)
    {
        new Ulam().F(1);
        System.Console.WriteLine();
        new Ulam().F(2);
        System.Console.WriteLine();
        new Ulam().F(3);
        System.Console.WriteLine();
        new Ulam().F(26);
        System.Console.WriteLine();
    }
}
\$\endgroup\$
  • \$\begingroup\$ Very slow: 46s for n=500, 6m for n=1000, 50m for n=2000. At that exponential rate, I believe it will take 5 or 6 days to process n=10K. \$\endgroup\$ – Richard II Sep 15 '14 at 19:10
0
\$\begingroup\$

Pyth, 27 25 bytes

<uaGh-sfq1lT.gksM.cG2GQS2

Try it online here.

<uaGh-sfq1lT.gksM.cG2GQS2Q   Implicit: Q=eval(input())
                             Trailing Q inferred
 u                    Q      Perform the following Q times...
                       S2    ... with G initialised to [1,2]:
                 .cG2          Get all 2-element combinations of G
               sM              Sum each pair
            .gk                Group them by value
                                 The groups are sorted by the result of the sum
       f                       Filter the groups, as T, keeping those where:
          lT                     Length of T
        q1                       Equal to 1
      s                        Flatten list
     -               G         Remove elements of the above which are already in G
    h                          Take the first of the remaining elements
                                 This is the smallest, as the grouping also sorted them
  aG                           Append this to G
<                        Q   Take the first Q elements, implicit print

Edit: golfed 2 bytes by performing summation before grouping. Previous version: <uaGh-mssdfq1lT.gsk.cG2GQS2

\$\endgroup\$
0
\$\begingroup\$

C, 478 bytes

#define R return
bs(x,v,l,h,r)unsigned x,*v,l,h,*r;{unsigned m;for(;l<=h;){m=(l+h)/2;if(x<v[m])h=m-1;else if(x>v[m])l=m+1;else{*r=m;R 1;}}*r=m;R 0;}
#include<stdlib.h>
unsigned*f(unsigned w){unsigned*u=0,i,k,m,y,z;if(w>1E6||w==0)R u;u=malloc(w*sizeof*u);if(!u)R u;k=0;u[k++]=1;if(w==1)R u;m=u[k++]=2;if(w==2)R u;l:for(i=0,y=0,z=k-1,++m;i<k;y+=bs(m-u[i],u,i+1,z,&z),++i)if(y>1||u[i]+(i+1!=k?u[i+1]:0)>m)break;if(m==0){free(u);u=0;R u;}if(y!=1)goto l;u[k++]=m;if(k< w)goto l;R u;}

In Tio now in 9 seconds it would find 10000 values (and in there print the first 100 values). The trick is using not linear search in the inner loop but binary search... These below are functions well indented and full readable (at last for me):

bsCopy(x,v,l,h,r)unsigned x,*v,l,h,*r;
{unsigned m;
 for(;l<=h;){m=(l+h)/2;if(x<v[m])h=m-1;else if(x>v[m])l=m+1;else{*r=m;R 1;}}
 *r=m;R 0;// in *r if return 0 the min index that fail else the index of find x
}

unsigned*fCopy(unsigned w)
{unsigned*u=0,i,k,m,y,z;
 if(w>1E6||w==0)R u;
 u=malloc(w*sizeof*u);
 if(!u)R u;
 k=0;u[k++]=1;if(w==1)R u;
   m=u[k++]=2;if(w==2)R u;//below I suppose m-u[i] is in the range (if exist in u) (i+1)..z 
 l: for(i=0,y=0,z=k-1,++m;i<k;y+=bsCopy(m-u[i],u,i+1,z,&z),++i)
          if(y>1||u[i]+(i+1!=k?u[i+1]:0)>m)break;
   if(m==0){free(u);u=0;R u;}
          if(y!=1)goto l;
   u[k++]=m;if(k< w)goto l;
 R u;
}
\$\endgroup\$
  • \$\begingroup\$ See if I can reduce something... \$\endgroup\$ – RosLuP 2 days ago
  • \$\begingroup\$ Something say me that in programming golfing is ok but it is not all... \$\endgroup\$ – RosLuP 2 days ago
  • 1
    \$\begingroup\$ 328 bytes \$\endgroup\$ – ceilingcat yesterday
  • \$\begingroup\$ @ceilingcat "z=k" for me is wrong because binary search (bs() function or your B()function) seems to me want as argument ranges (I don't know if it is right too...) so in the function who call bin search it has to be z=k-1 \$\endgroup\$ – RosLuP yesterday
0
\$\begingroup\$

APL(NARS), 278 char, 556 bytes

∇u←p w;m;y;i;k;z;r;bs
bs←{(x l h)←⍵⋄l>h:0,h⋄x<⍺[t←⌊2÷⍨l+h]:⍺∇x,l,t-1⋄x>⍺[t]:⍺∇x,(t+1),h⋄1,t}
u←⍬  ⋄→0×⍳(w>1E6)∨w≤0
u←u,1⋄→0×⍳w=1
u←u,2⋄→0×⍳w=2⋄k←m←2
i←1⋄y←0⋄m+←1⋄z←k
→7×⍳(y>1)∨i>k⋄→7×⍳m<u[i]+{i=k:0⋄u[i+1]}⋄r←u bs(m-u[i]),(i+1),z⋄y+←↑r⋄z←2⊃r⋄i+←1⋄→6
→5×⍳y≠1⋄u←u,m⋄k+←1⋄→5×⍳k<w
∇

it would be the translation in APL of C one I sent. It seems i not understand when to use ∇∇ in place of ∇... possible ∇∇ is used when there is one argument is one function (and not one other type). "u bs x, a,b" should be the bin search in "u" array for the value "x" in the range a..b; it would return 1, indexWhereFind or 0, indexWhereEndOfsearch. With argument 200 p function take +- a minute here...

  p 100
1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69 72 77 82 87 97 99 102 106 114 126 
  131 138 145 148 155 175 177 180 182 189 197 206 209 219 221 236 238 241 243 253 
  258 260 273 282 309 316 319 324 339 341 356 358 363 370 382 390 400 402 409 412 
  414 429 431 434 441 451 456 483 485 497 502 522 524 544 546 566 568 585 602 605 
  607 612 624 627 646 668 673 685 688 690 
  p¨1 2 3 4
1  1 2  1 2 3  1 2 3 4 
\$\endgroup\$
  • \$\begingroup\$ ∇∇ in a dop refers to the operator itself while refers to the derived function consisting of the operator with its operand(s). So in a monadic operator is the same as (⍺⍺∇∇) while in a dyadic operator it means (⍺⍺∇∇⍵⍵). \$\endgroup\$ – Adám 17 mins ago

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.