Sylvester's sequence: Difference between revisions
(Added Prolog solution) |
(→{{header|ALGOL 68}}: Corrected spelling of reciprocal - thanks to Gerard Schildberger for showing me the error of my ways...) |
||
Line 25:
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Uses Algol 68G's LONG LONG INT and LONG LONG REAL which have specifiable precision. The sum of the
<lang algol68>BEGIN # calculate elements of Sylvestor's Sequence #
PR precision 200 PR # set the number of digits for LONG LONG modes #
Line 44:
# find the first 10 elements of Sylvestor's Seuence #
[]LONG LONG INT seq = SYLVESTOR 10;
# show the sequence and sum the
LONG LONG REAL
FOR i FROM LWB seq TO UPB seq DO
print( ( whole( seq[ i ], 0 ), newline ) );
OD;
print( ( "Sum of
END
</lang>
Line 65:
12864938683278671740537145998360961546653259485195807
165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443
Sum of
</pre>
|
Revision as of 20:29, 5 June 2021
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
ALGOL 68
Uses Algol 68G's LONG LONG INT and LONG LONG REAL which have specifiable precision. The sum of the reciprocals in the output has been manually edited to replace a large number of nines with ... to reduce the width. <lang algol68>BEGIN # calculate elements of Sylvestor's Sequence #
PR precision 200 PR # set the number of digits for LONG LONG modes # # returns an array set to the forst n elements of Sylvestor's Sequence # # starting from 2, the elements are the product of the previous # # elements plus 1 # OP SYLVESTOR = ( INT n )[]LONG LONG INT: BEGIN [ 1 : n ]LONG LONG INT result; LONG LONG INT product := 2; result[ 1 ] := 2; FOR i FROM 2 TO n DO result[ i ] := product + 1; product *:= result[ i ] OD; result END; # find the first 10 elements of Sylvestor's Seuence # []LONG LONG INT seq = SYLVESTOR 10; # show the sequence and sum the reciprocals # LONG LONG REAL reciprocal sum := 0; FOR i FROM LWB seq TO UPB seq DO print( ( whole( seq[ i ], 0 ), newline ) ); reciprocal sum +:= 1 / seq[ i ] OD; print( ( "Sum of reciprocals: ", reciprocal sum, newline ) )
END </lang>
- Output:
2 3 7 43 1807 3263443 10650056950807 113423713055421844361000443 12864938683278671740537145998360961546653259485195807 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 Sum of reciprocals: +9.99999999999999999999999999999999999999999...999999999999999999999999999964e -1
C++
<lang cpp>#include <iomanip>
- include <iostream>
- include <boost/rational.hpp>
- include <boost/multiprecision/cpp_int.hpp>
using integer = boost::multiprecision::cpp_int; using rational = boost::rational<integer>;
integer sylvester_next(const integer& n) {
return n * n - n + 1;
}
int main() {
std::cout << "First 10 elements in Sylvester's sequence:\n"; integer term = 2; rational sum = 0; for (int i = 1; i <= 10; ++i) { std::cout << std::setw(2) << i << ": " << term << '\n'; sum += rational(1, term); term = sylvester_next(term); } std::cout << "Sum of reciprocals: " << sum << '\n';
}</lang>
- Output:
First 10 elements in Sylvester's sequence: 1: 2 2: 3 3: 7 4: 43 5: 1807 6: 3263443 7: 10650056950807 8: 113423713055421844361000443 9: 12864938683278671740537145998360961546653259485195807 10: 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 Sum of reciprocals: 27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920805/27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920806
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 [ dup sq swap - 1 + ] lfrom-by ;
"First 10 elements of Sylvester's sequence:" print 10 lsylvester ltake dup [ . ] leach 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
Or, in other words, the sum is 2739245…3920805/2739245…3920806
.
Haskell
<lang haskell>sylvester :: [Integer] sylvester = map s [0 ..]
where s 0 = 2 s n = succ $ foldr ((*) . s) 1 [0 .. pred n]
main :: IO () main = do
putStrLn "First 10 elements of Sylvester's sequence:" putStr $ unlines $ map show $ take 10 sylvester
putStr "\nSum of reciprocals by sum over map: " print $ sum $ map ((1 /) . fromInteger) $ take 10 sylvester
putStr "Sum of reciprocals by fold: " print $ foldr ((+) . (1 /) . fromInteger) 0 $ 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 by sum over map: 0.9999999999999999 Sum of reciprocals by fold: 1.0
Julia
<lang julia>sylvester(n) = (n == 1) ? big"2" : prod(sylvester, 1:n-1) + big"1"
foreach(n -> println(rpad(n, 3), " => ", sylvester(n)), 1:10)
println("Sum of reciprocals of first 10: ", sum(big"1.0" / sylvester(n) for n in 1:10))
</lang>
- Output:
1 => 2 2 => 3 3 => 7 4 => 43 5 => 1807 6 => 3263443 7 => 10650056950807 8 => 113423713055421844361000443 9 => 12864938683278671740537145998360961546653259485195807 10 => 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 Sum of reciprocals of first 10: 0.9999999999999999999999999999999999999999999999999999999999999999999999999999914
Perl
<lang perl>use strict; use warnings; use feature 'say'; use List::Util 'reduce'; use Math::AnyNum ':overload'; local $Math::AnyNum::PREC = 845;
my(@S,$sum); push @S, 1 + reduce { $a * $b } @S for 0..10; shift @S; $sum += 1/$_ for @S;
say "First 10 elements of Sylvester's sequence: @S"; say "\nSum of the reciprocals of first 10 elements: " . float $sum;</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
Phix
standard precision
atom n, rn = 0, lim = power(2,iff(machine_bits()=32?53:64)) for i=1 to 10 do n = iff(i=1?2:n*n-n+1) printf(1,iff(n<=lim?"%d: %d\n":"%d: %g\n"),{i,n}) rn += 1/n end for printf(1,"sum of reciprocals: %g\n",{rn})
- Output:
1: 2 2: 3 3: 7 4: 43 5: 1807 6: 3263443 7: 10650056950807 8: 1.13424e+26 9: 1.2865e+52 10: 1.65507e+104 sum of reciprocals: 1
mpfr version
Note the (minimal) precision settings of 698 and 211 were found by trial and error (ie larger values gain nothing but smaller ones lose accuracy).
include mpfr.e mpz n = mpz_init(2), nm1 = mpz_init() mpfr_set_default_prec(698) mpfr {rn, tmp} = mpfr_inits(2) for i=1 to 10 do if i>1 then mpz_sub_ui(nm1,n,1) mpz_mul(n,nm1,n) mpz_add_ui(n,n,1) end if printf(1,"%d: %s\n",{i,mpz_get_str(n)}) mpfr_set_z(tmp,n) mpfr_si_div(tmp,1,tmp) mpfr_add(rn,rn,tmp) end for printf(1,"sum of reciprocals: %s\n",{shorten(mpfr_sprintf("%.211Rf",rn))})
- Output:
1: 2 2: 3 3: 7 4: 43 5: 1807 6: 3263443 7: 10650056950807 8: 113423713055421844361000443 9: 12864938683278671740537145998360961546653259485195807 10: 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 sum of reciprocals: 0.999999999999999999...99999999999999999635 (213 digits)
Prolog
<lang prolog>sylvesters_sequence(N, S, R):-
sylvesters_sequence(N, S, 2, R, 0).
sylvesters_sequence(0, [X], X, R, S):-
!, R is S + 1 rdiv X.
sylvesters_sequence(N, [X|Xs], X, R, S):-
Y is X * X - X + 1, M is N - 1, T is S + 1 rdiv X, sylvesters_sequence(M, Xs, Y, R, T).
main:-
sylvesters_sequence(9, Sequence, Sum), writeln('First 10 elements in Sylvester\'s sequence:'), forall(member(S, Sequence), writef('%t\n', [S])), N is numerator(Sum), D is denominator(Sum), writef('\nSum of reciprocals: %t / %t\n', [N, D]).</lang>
- Output:
First 10 elements in Sylvester's sequence: 2 3 7 43 1807 3263443 10650056950807 113423713055421844361000443 12864938683278671740537145998360961546653259485195807 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 Sum of reciprocals: 27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920805 / 27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920806
Python
<lang python>Sylvester's sequence
from functools import reduce from itertools import count, islice
- sylvester :: [Int]
def sylvester():
Non-finite stream of the terms of Sylvester's sequence. (OEIS A000058) def go(n): return 1 + reduce( lambda a, x: a * go(x), range(0, n), 1 ) if 0 != n else 2
return map(go, count(0))
- ------------------------- TEST -------------------------
- main :: IO ()
def main():
First terms, and sum of reciprocals.
print("First 10 terms of OEIS A000058:") xs = list(islice(sylvester(), 10)) print('\n'.join([ str(x) for x in xs ]))
print("\nSum of the reciprocals of the first 10 terms:") print( reduce(lambda a, x: a + 1 / x, xs, 0) )
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
First 10 terms of OEIS A000058: 2 3 7 43 1807 3263443 10650056950807 113423713055421844361000443 12864938683278671740537145998360961546653259485195807 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 Sum of the reciprocals of the first 10 terms: 0.9999999999999999
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
REXX
<lang rexx>/*REXX pgm finds N terms of the Sylvester's sequence & the sum of the their reciprocals.*/ parse arg n . /*obtain optional argument from the CL.*/ if n== | n=="," then n= 10 /*Not specified? Then use the default.*/ numeric digits max(9, 2**(n-7)*13 + 1) /*calculate how many dec. digs we need.*/ @.0= 2 /*the value of the 1st Sylvester number*/ $= 0
do j=0 for n; jm= j - 1 /*calculate the Sylvester sequence. */ if j>0 then @.j= @.jm**2 - @.jm + 1 /*calculate a Sylvester sequence num.*/ say 'Sylvester('j") ──► " @.j /*display the Sylvester index & number.*/ $= $ + 1 / @.j /*add its reciprocal to the recip. sum.*/ end /*j*/
say numeric digits digits()-1 say 'sum of the first ' n " reciprocals using" digits() 'decimal digits: ' $ / 1</lang>
- output when using the default inputs:
Sylvester(0) ──► 2 Sylvester(1) ──► 3 Sylvester(2) ──► 7 Sylvester(3) ──► 43 Sylvester(4) ──► 1807 Sylvester(5) ──► 3263443 Sylvester(6) ──► 10650056950807 Sylvester(7) ──► 113423713055421844361000443 Sylvester(8) ──► 12864938683278671740537145998360961546653259485195807 Sylvester(9) ──► 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 sum of the first 10 reciprocals using 104 decimal digits: 1
Wren
<lang ecmascript>import "/big" for BigInt, BigRat
var sylvester = [BigInt.two] var prod = BigInt.two var count = 1 while (true) {
var next = prod + 1 sylvester.add(next) count = count + 1 if (count == 10) break prod = prod * next
} System.print("The first 10 terms in the Sylvester sequence are:") System.print(sylvester.join("\n"))
var sumRecip = sylvester.reduce(BigRat.zero) { |acc, s| acc + BigRat.new(1, s) } System.print("\nThe sum of their reciprocals as a rational number is:") System.print (sumRecip) System.print("\nThe sum of their reciprocals as a decimal number (to 211 places) is:") System.print(sumRecip.toDecimal(211))</lang>
- Output:
The first 10 terms in the Sylvester sequence are: 2 3 7 43 1807 3263443 10650056950807 113423713055421844361000443 12864938683278671740537145998360961546653259485195807 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443 The sum of their reciprocals as a rational number is: 27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920805/27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920806 The sum of their reciprocals as a decimal number (to 211 places) is: 0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999635