[seqfan] Re: A057652 has no more terms below 10^4

[hv at crypt.org]

Alonso Del Arte <alonso.delarte at gmail.com> wrote:
:Very interesting, Hugo. I have access to C but not Perl, though on the other
:hand, Perl is open source and I could download it for free?

Yes: start at <http://www.perl.org>.

For speed, pure number crunching of this type is about the worst task to
throw at scripting languages like perl - they are typically 10-100 times
slower than C for this. For other tasks, like text processing or I/O,
the performance is much more closely comparable to C.

However, they are great for rapid prototyping, so I can get several
algorithms implemented and debugged (and get a good idea of relative
performance) in the time I could get any one of them working in C.

And often, it turns out, this (relatively) slow performance for numeric
work is still good enough to get the required answer - I'd guess that for
some 75% of the "+hard +more" sequences I've extended, I needed only perl.

The approach I used for calculating the lucky numbers is very simple:

  my @lucky;  # list of lucky numbers, excluding 1
  my @skipped;  # for each lucky number, count those skipped since last deletion
  my $n = 1;

  CANDIDATE: while ($n < $limit) {
    $n += 2;
    for my $index (0 .. $#lucky) {
      if (++$skipped[$index] == $lucky[$index]) {
        $skipped[$index] = 0;  # this is a deletion
        next CANDIDATE;
      }
    }
	push @lucky, $n;  # we reached the end of the list without getting deleted
    push @skipped, @lucky + 1;  # +1 to account for 1 itself
    print $n;
  }

For calculating a large number of them, the trick will be to constrain the
memory use: this variant stores 2 integers for each lucky number seen.

Hugo