Ulam numbers: Difference between revisions

 

;Task:

 

 

{{trans|Python}}

 

I n <= 2

R n

L(p) 5

V n = 10 ^ p

 

{{out}}

The 1000th Ulam number is 12294

The 10000th Ulam number is 132788

</pre>

 

=={{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();

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

 

It has been compiled with option <code>-d:release</code> which means that all runtime checks are done but debugging data is limited.

 

func ulam(n: Positive): int =

echo &"The {n}{suffix} Ulam number is {ulam(n)}."

n *= 10

 

{{out}}

It has been compiled with the same option as the other version.

 

 

func ulam(n: Positive): int =

echo &"The {n}th Ulam number is {ulam(n)}."

n *= 10

 

{{out}}

=={{header|Pascal}}==

{{works with|Free Pascal}} like GO,PHIX who was first

{$IFDEF FPC}

{$MODE DELPHI}

setlength(Ulams,0);

end.

<pre> Ulam(1) 1

Ulam(10) 18

=={{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

 

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.*/

z= z + 1 /*bump next possible term. */

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}}

=={{header|Sidef}}==

{{trans|Perl}}

 

static u = Set(1,2)

for k in (1..3) {

say "The 10^#{k}-th Ulam number is: #{ulam(10**k)}"

{{out}}

<pre>

The 10^2-th Ulam number is: 690

The 10^3-th Ulam number is: 12294

</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}}