Peter
Peter Campbell Smith

Aesthetics and a
fast-growing sequence

Weekly challenge 173 — 11 July 2022

Week 173 - 11 Jul 2022

Task 2

Task — Sylvester’s sequence

Write a script to generate first 10 members of Sylvester's sequence. For more information, please refer to the Wikipedia page.

Analysis

Sylvester the cat

I had rather hoped that this was discovered by the eponymous cat, but it seems that James Joseph Sylvester was responsible. The sequence starts with 2, 3, and each subsequent term is the product of all the preceding ones, plus one.

A little reflection reveals that:

  • This is going to get big as fast as a pumpkin
  • So we'd better resort to Math::BigInt

We can save microseconds by noting that term n really only depends on term n - 1. Specifically:

syl(n) = (syl(n - 1) - 1) * syl(n - 1) + 1

And once we have conquered the challenge of expressing that in BigInt-ian:

$sylvester[$j] = Math::BigInt->new(0)  # zero
  ->badd($sylvester[$j - 1])     # plus preceding term
  ->bsub(Math::BigInt->new(1))   # minus 1 
  ->bmul($sylvester[$j - 1])     # times preceding one
  ->badd(Math::BigInt->new(1));  # plus 1

... we have our solution.

We are asked for the first 10 terms, and the tenth turns out to be 1655066473245199641984681954444391800175131527063774978418 51388766535868639572406808911988131737645185443, which confirms the decision to use BigInt.

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-07-11
# PWC 173 task 2

use v5.26;
use strict;
use warnings;
use utf8;
binmode(STDOUT, ':utf8');
use Math::BigInt;

my (@sylvester, $j);

# first 2 terms are given
$sylvester[0] = Math::BigInt->new(2);
$sylvester[1] = Math::BigInt->new(3);

# loop over 10 terms
for $j (0 .. 9) {
    if ($j > 1) {
        $sylvester[$j] = Math::BigInt->new(0)  # zero
            ->badd($sylvester[$j - 1])         # plus the preceding term
            ->bsub(Math::BigInt->new(1))       # minus 1 (to get product of all terms up to preceding one)
            ->bmul($sylvester[$j - 1])         # times the preceding one
            ->badd(Math::BigInt->new(1));      # plus 1
    }
    say qq[sylvester[$j] = ] . $sylvester[$j]->bstr();
}

Output


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] = 128649386832786717405371459983609615466532
   59485195807
sylvester[9] = 165506647324519964198468195444439180017513
   152706377497841851388766535868639572406808911988131737
   645185443

The content of this website which has been created by
Peter Campbell Smith is hereby placed in the public domain