Sylvester's sequence
This page uses content from Wikipedia. The original article was at Sylvester's sequence. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
In number theory, Sylvester's sequence is an integer sequence in which each term of the sequence is the product of the previous terms, plus one.
Its values grow doubly exponentially, and the sum of its reciprocals forms a series of unit fractions that converges to 1 more rapidly than any other series of unit fractions with the same number of terms. Further, the sum of the first k terms of the infinite series of reciprocals provides the closest possible underestimate of 1 by any k-term Egyptian fraction.
- Task
- Write a routine (function, procedure, generator, whatever) to calculate Sylvester's sequence.
- Use that routine to show the values of the first 10 elements in the sequence.
- Show the sum of the reciprocals of the first 10 elements on the sequence;
- See also
Factor
Note that if the previous element of the sequence is x, the next element is x2-x+1.
<lang factor>USING: io kernel lists lists.lazy math prettyprint ;
- lsylvester ( -- list ) 2 [ [ sq ] [ - 1 + ] bi ] lfrom-by ;
"First 10 elements of Sylvester's sequence:" print 10 lsylvester ltake dup [ pprint bl ] leach nl nl
"Sum of the reciprocals of first 10 elements:" print 0 [ recip + ] foldl .</lang>
- Output:
First 10 elements of Sylvester's sequence: 2 3 7 43 1807 3263443 10650056950807 113423713055421844361000443 12864938683278671740537145998360961546653259485195807 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 Sum of the reciprocals of first 10 elements: 27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920805/27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920806
Haskell
<lang haskell>sylvester :: [Integer] sylvester = map s [0..]
where s 0 = 2 s n = product (map s [0..n-1]) + 1
main :: IO () main = do
putStrLn "First 10 elements of Sylvester's sequence:" putStr $ unlines $ map show $ take 10 sylvester putStr "Sum of reciprocals: " putStrLn $ show $ sum $ map ((1/) . fromInteger) $ take 10 sylvester</lang>
- Output:
First 10 elements of Sylvester's sequence: 2 3 7 43 1807 3263443 10650056950807 113423713055421844361000443 12864938683278671740537145998360961546653259485195807 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 Sum of reciprocals: 0.9999999999999999
Julia
<lang julia>sylvester(n) = (n == 1) ? big"2" : prod(i -> sylvester(i), 1:n-1) + big"1"
foreach(n -> println(rpad(n, 3), " => ", sylvester(n)), 1:10)
</lang>
- Output:
1 => 2 2 => 3 3 => 7 4 => 43 5 => 1807 6 => 3263443 7 => 10650056950807 8 => 113423713055421844361000443 9 => 12864938683278671740537145998360961546653259485195807 10 => 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443
Raku
<lang perl6>my @S = {1 + [*] @S[^($++)]} … *;
put 'First 10 elements of Sylvester\'s sequence: ', @S[^10];
say "\nSum of the reciprocals of first 10 elements: ", sum @S[^10].map: { FatRat.new: 1, $_ };</lang>
- Output:
First 10 elements of Sylvester's sequence: 2 3 7 43 1807 3263443 10650056950807 113423713055421844361000443 12864938683278671740537145998360961546653259485195807 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 Sum of the reciprocals of first 10 elements: 0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999635