Ulam numbers: Difference between revisions
(→{{header|REXX}}: updated the program to just find a particular Ulam number.) |
(add freebasic) |
||
Line 15: | Line 15: | ||
* [[oeis:A002858|OEIS Ulam numbers]] |
* [[oeis:A002858|OEIS Ulam numbers]] |
||
<br><br> |
<br><br> |
||
=={{header|FreeBSIC}}== |
|||
<lang freebasic>redim as uinteger ulam(1 to 2) |
|||
ulam(1) = 1 : ulam(2) = 2 |
|||
function get_ulam( n as uinteger, ulam() as uinteger ) as uinteger |
|||
dim as uinteger nu = ubound(ulam), c, r, s, t, i |
|||
if n <= nu then return ulam(n) 'if we have already calculated this one, just return it |
|||
'otherwise, calculate it and all intermediate terms |
|||
redim preserve ulam(1 to n) |
|||
for t = nu+1 to n |
|||
i = ulam(t-1) |
|||
while true |
|||
i += 1 : c = 0 |
|||
for r = 1 to t-2 |
|||
for s = r+1 to t-1 |
|||
if ulam(r) + ulam(s) = i then |
|||
if c = 1 then continue while |
|||
c += 1 |
|||
end if |
|||
next s |
|||
next r |
|||
if c = 0 then continue while 'I'm not 100% sure this is even possible... |
|||
ulam(t) = i |
|||
exit while |
|||
wend |
|||
next t |
|||
return ulam(n) |
|||
end function |
|||
for i as uinteger = 1 to 4 |
|||
print 10^i, get_ulam(10^i, ulam()) |
|||
next i</lang> |
|||
{{out}} |
|||
<pre> 10 18 |
|||
100 690 |
|||
1000 12294 |
|||
10000 132788</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
Revision as of 10:22, 2 December 2020
With the following initial conditions:
u1 = 1 u2 = 2
we define the nth Ulam number un as the number that is greater than un-1 and uniquely written as a sum of two different Ulam numbers ui (<n) and uj (<n).
- Task
Write a function to generate the n-th Ulam number.
- References
FreeBSIC
<lang freebasic>redim as uinteger ulam(1 to 2) ulam(1) = 1 : ulam(2) = 2
function get_ulam( n as uinteger, ulam() as uinteger ) as uinteger
dim as uinteger nu = ubound(ulam), c, r, s, t, i if n <= nu then return ulam(n) 'if we have already calculated this one, just return it 'otherwise, calculate it and all intermediate terms redim preserve ulam(1 to n) for t = nu+1 to n i = ulam(t-1) while true i += 1 : c = 0 for r = 1 to t-2 for s = r+1 to t-1 if ulam(r) + ulam(s) = i then if c = 1 then continue while c += 1 end if next s next r if c = 0 then continue while 'I'm not 100% sure this is even possible... ulam(t) = i exit while wend next t return ulam(n)
end function
for i as uinteger = 1 to 4
print 10^i, get_ulam(10^i, ulam())
next i</lang>
- Output:
10 18 100 690 1000 12294 10000 132788
Go
<lang go>package main
import "fmt"
func ulam(n int) int {
ulams := []int{1, 2} set := map[int]bool{1: true, 2: true} i := 3 for { count := 0 for j := 0; j < len(ulams); j++ { _, ok := set[i-ulams[j]] if ok && ulams[j] != (i-ulams[j]) { count++ if count > 2 { break } } } if count == 2 { ulams = append(ulams, i) set[i] = true if len(ulams) == n { break } } i++ } return ulams[n-1]
}
func main() {
for n := 10; n <= 10000; n *= 10 { fmt.Println("The", n, "\bth Ulam number is", ulam(n)) }
}</lang>
- Output:
The 10th Ulam number is 18 The 100th Ulam number is 690 The 1000th Ulam number is 12294 The 10000th Ulam number is 132788
Haskell
Lazy List
<lang haskell> import Data.List
ulam
:: Integral i => Int -> i
ulam 1 = 1 ulam 2 = 2 ulam n
| n > 2 = ulams !! (n-1)
ulams
:: Integral n => [n]
ulams = 1:2:(nexts [2,1]) nexts us = u: (nexts (u:us))
where n = length us [u] = head . filter isSingleton . group . sort $ [v | i <- [0 .. n-2], j <- [i+1 .. n-1] , let s = us !! i , let t = us !! j , let v = s+t , v > head us ]
isSingleton :: [a] -> Bool isSingleton as
| length as == 1 = True | otherwise = False</lang>
Phix
<lang Phix>function ulam(integer n)
sequence ulams = {1, 2}, sieve = {1, 1} integer u := 2 while true do integer s = u+ulams[$-1] sieve &= repeat(0,s-length(sieve)) for i=1 to length(ulams)-1 do sieve[u+ulams[i]] += 1 end for u = find(1,sieve,u+1) ulams &= u if length(ulams)=n then exit end if end while return ulams[n]
end function
for p=1 to 4 do
integer n = power(10,p) printf(1,"The %,d%s Ulam number is %,d\n",{n,ord(n),ulam(n)})
end for</lang>
- Output:
The 10th Ulam number is 18 The 100th Ulam number is 690 The 1,000th Ulam number is 12,294 The 10,000th Ulam number is 132,788
Raku
<lang perl6>my @ulams = 1, 2, &next-ulam … *;
sub next-ulam {
state $i = 1; state @sums = 0,1,1; my $last = @ulams[$i]; (^$i).map: { @sums[@ulams[$_] + $last]++ }; ++$i; quietly ($last ^.. *).first: { @sums[$_] == 1 };
}
for 1 .. 4 {
say "The {10**$_}th Ulam nmber is: ", @ulams[10**$_ - 1]
}</lang>
- Output:
The 10th Ulam nmber is: 18 The 100th Ulam nmber is: 690 The 1000th Ulam nmber is: 12294 The 10000th Ulam nmber is: 132788
REXX
<lang rexx>/*REXX program finds and displays the Nth Ulam number (or a series of various numbers).*/ parse arg highs /*obtain optional argument from the CL.*/ if highs= | highs="," then highs= 10 100 1000 /*Not specified? Then use the defaults.*/
do i=1 for words(highs) z= Ulam( word(highs, i) ) /*define the first two Ulam numbers. */ say 'the ' commas(#)th(#) ' Ulam number is: ' commas(@.#) end /*i*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _ th: parse arg th; return word('th st nd rd', 1 + (th//10)*(th//100%10\==1)*(th//10<4)) /*──────────────────────────────────────────────────────────────────────────────────────*/ Ulam: parse arg n; @.1= 1; @.2= 2 /*define the first two Ulam numbers. */
#= 2 /*the number of Ulam numbers (so far).*/ do j=3; !.= /*search for numbers in this range. */ mx= 0 /*define the maximum sum (so far). */ do a=1 for # /* [↑] compute all possible Ulam sums.*/ do b=a+1 to # /*compute a sum from two Ulam numbers. */ s= @.a + @.b /*compute a sum from two Ulam numbers. */ if s<@.# then iterate /*Is the sum is too small? Then skip. */ !.s= !.s s /*append a sum to a list of sums for S.*/ mx= max(mx, s) /*obtain the maximum sum, a later limit*/ end /*b*/ end /*a*/
do f=@.#+1 to mx /* [↓] find if the sum is unique. */ if !.f== then iterate /*Is the number defined? No, then skip*/ if words(!.f)>1 then iterate /*Is the sum unique? " " " */ #= # + 1 /*bump the count of Ulam numbers found.*/ @.#= strip(!.f) /*elide any superfluous blanks in list.*/ if #==n then leave j /*Found the Nth number? Then we're done*/ leave /*now, go and find the next Ulam number*/ end /*f*/ end /*j*/; return @.# /*return the Nth Ulam number to caller.*/</lang>
- output when using the default inputs:
the 10th Ulam number is: 18 the 100th Ulam number is: 690 the 1,000th Ulam number is: 12,294
Ring
<lang ring> load "stdlib.ring"
limit = 12500 Ulam = [] add(Ulam,1) add(Ulam,2)
for n = 3 to limit
flag = 0 count = 0 len = len(Ulam) for x = 1 to len-1 for y = x+1 to len if Ulam[x] + Ulam[y] = n flag = 1 count = count + 1 ok next next if flag = 1 and count = 1 add(Ulam,n) ln = len(Ulam) if ln = 10 see "The 10th Ulam number is: " + n + nl ok if ln = 100 see "The 100th Ulam number is: " + n + nl ok if ln = 1000 see "The 1000th Ulam number is: " + n + nl ok if ln = 10000 see "The 10000th Ulam number is: " + n + nl ok ok
next </lang> Output:
The 10th Ulam number is: 18 The 100th Ulam number is: 690 The 1000th Ulam number is: 12294 The 10000th Ulam number is: 132788
Wren
<lang ecmascript>import "/set" for Set
var ulam = Fn.new() { |n|
var ulams = [1, 2] var set = Set.new(ulams) var i = 3 while (true) { var count = 0 for (j in 0...ulams.count) { if (set.contains(i - ulams[j]) && ulams[j] != (i - ulams[j])) { count = count + 1 if (count > 2) break } } if (count == 2) { ulams.add(i) set.add(i) if (ulams.count == n) break } i = i + 1 } return ulams[-1]
}
var n = 1 while (true) {
n = n * 10 System.print("The %(n)th Ulam number is %(ulam.call(n))") if (n == 10000) break
}</lang>
- Output:
The 10th Ulam number is 18 The 100th Ulam number is 690 The 1000th Ulam number is 12294 The 10000th Ulam number is 132788