Ulam numbers: Difference between revisions

<big><big> u₂ = 2 </big></big>

 

 

 

;Task:

 

 

* &nbsp; [[oeis:A002858|OEIS Ulam numbers]]

<br><br>

 

=={{header|AWK}}==

# syntax: GAWK -f ULAM_NUMBERS.AWK

BEGIN {

exit(0)

}

{{out}}

<pre>

=={{header|C}}==

{{trans|Phix}}

#include <stdlib.h>

#include <string.h>

printf("Elapsed time: %.3f seconds\n", (finish - start + 0.0)/CLOCKS_PER_SEC);

return 0;

 

{{out}}

=={{header|C++}}==

{{trans|Phix}}

#include <chrono>

#include <iostream>

std::chrono::duration<double> duration(end - start);

std::cout << "Elapsed time: " << duration.count() << " seconds\n";

 

{{out}}

Elapsed time: 9.09242 seconds

</pre>

 

=={{header|FreeBASIC}}==

ulam(1) = 1 : ulam(2) = 2

 

print 10^i, get_ulam(10^i, ulam())

next i

 

{{out}}

===Version 1===

{{trans|Wren}}

 

import "fmt"

fmt.Println("The", n, "\bth Ulam number is", ulam(n))

}

 

{{out}}

 

Although not shown here, the 100,000th Ulam number (1,351,223) is computed in about 13.5 seconds.

 

import (

}

fmt.Println("\nTook", time.Since(start))

 

{{out}}

 

As mentioned in the Wren version 3 example, you need to know how much memory to allocate in advance.

 

import (

}

fmt.Println("\nTook", time.Since(start))

 

{{out}}

 

===Lazy List===

import Data.List

 

isSingleton as

| length as == 1 = True

 

=={{header|Java}}==

{{trans|Phix}}

public static void main(String[] args) {

long start = System.currentTimeMillis();

for (int n = 1; n <= 100000; n *= 10) {

}

long finish = System.currentTimeMillis();

}

 

return newArray;

}

 

{{out}}

Ulam(100000) = 1351223

Elapsed time: 9.098 seconds

</pre>

 

=={{header|Julia}}==

{{trans|Wren}}

ulams = [1, 2]

memoized = Set([1, 2])

@time println("The ", n, "th Ulam number is: ", nthUlam(n))

end

<pre>

The 10th Ulam number is: 18

=={{header|Lua}}==

Implemented from scratch, but algorithmically equivalent to other solutions where a running count of number-of-ways-to-reach-sum is maintained in order to sieve candidate values.

local ulams, nways, i = { 1,2 }, { 0,0,1 }, 3

repeat

local s, u, e = os.clock(), ulam(n), os.clock()

print(string.format("%dth is %d (%f seconds elapsed)", n, u, e-s))

{{out}}

Times are Lua 5.4 on i7-2600@3.4GHz

100000th is 1351223 (277.824000 seconds elapsed)</pre>

 

=={{header|Perl}}==

{{trans|Julia}}

use warnings;

use feature <say state>;

}

 

{{out}}

<pre>The 10th Ulam number is: 18

 

=={{header|Phix}}==

{{out}}

<pre>

Raku (on repl.it) 9mins 50s,

FreeBASIC 17mins 44s, and I cancelled XPL0 (on EXPL32) after 53 minutes.

 

The above algorithm can also yield "The 100,000th Ulam number is 1,351,223" in 1 minute and 40s, for me.

<small>(I fully expect translations of this better algorithm to run even faster, btw)</small>

 

=={{header|Python}}==

{{trans|XPL0}}

 

def ulam(n):

 

print("\nElapsed time:", time.time() - t0)

 

{{out}}

=={{header|Raku}}==

 

 

sub next-ulam {

for 1 .. 4 {

say "The {10**$_}th Ulam number is: ", @ulams[10**$_ - 1]

{{out}}

<pre>The 10th Ulam number is: 18

=={{header|REXX}}==

{{trans|Wren}}

This REXX version has several speed improvements.

parse arg $ /*obtain optional argument from the CL.*/

if $='' | $="," then $= 10 100 1000 10000 /*Not specified? Then use the defaults.*/

say 'the ' commas(#)th(#) ' Ulam number is: ' commas(x)

end /*k*/

exit 0 /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

th: parse arg th; return word('th st nd rd', 1 + (th//10)*(th//100%10\==1)*(th//10<4))

/*──────────────────────────────────────────────────────────────────────────────────────*/

z= 3 /*value of next possible term in seq. */

do until #==n

cnt= 0

end

end /*j*/

 

end

end /*until*/

{{out|output|text=&nbsp; when using the default input of: &nbsp; &nbsp; <tt> 10 &nbsp; 100 &nbsp; 1000 &nbsp; 10000 </tt>}}

<pre>

 

=={{header|Ring}}==

load "stdlib.ring"

 

ok

next

Output:

<pre>

=={{header|Rust}}==

{{trans|Phix}}

let mut ulams = vec![1, 2];

let mut sieve = vec![1, 1];

}

println!("Elapsed time: {:.2?}", start.elapsed());

 

{{out}}

Ulam(100000) = 1351223

Elapsed time: 10.68s

</pre>

 

===Version 1===

{{libheader|Wren-set}}

 

var ulam = Fn.new() { |n|

System.print("The %(n)th Ulam number is %(ulam.call(n))")

if (n == 10000) break

 

{{out}}

{{libheader|Wren-fmt}}

The above version is reasonably efficient and runs in about 21.6 seconds on my machine (Intel Core i7-8565U). The following version, which builds up a sieve as it goes along, is more than 3 times faster.

 

var ulam = Fn.new { |n|

Fmt.print("The $,r Ulam number is $,d", n, ulam.call(n))

}

 

{{out}}

 

The only downside with this version is that you need to know how much memory to allocate in advance.

 

var ulam = Fn.new { |n|

if (n > 100000) break

}

 

{{out}}

Ulam number in 24.7 seconds on a Pi4.

 

int N;

def Max = 1_352_000; \enough for 100_000th Ulam number

N:= N*10;

until N > 100_000;

 

{{out}}