A005520 (Complexity)

[hv at crypt.org]

franktaw at netscape.net wrote:
:I note that of the numbers shown for this sequence, the only composite 
:ones are 4, 10, 22, and 1438.  Are there any others?

I don't know python well enough to adapt Tim Peters' script to show
the minimum, but the perl code below may be of use if you have more
RAM than I do: code below costs me 7.5 minutes and about 200MB to
get to a(50), and will grow roughly proportionally to A000792(n).
It should be accurate for n: A000792(n) < 2^32.

I can't see a way to find a(n) without calculating A005245(k) for
at least all k up to a(n), but it is an interesting question: I'll
try to track down some of the references from UPINT F26.

I wonder also whether there are any examples other than n=26 where
a(n+1) > 2a(n).

Hugo
---
#!/usr/bin/perl -w
use strict;
use Math::Pari qw/ isprime /;
my @a = ("", pack "L", 1);
my $v = ""; vec($v, 1, 1) = 1;
my $prev = 2;

for (my $n = 2; 1; ++$n) {
  my($min, $max) = ($prev * 2, 0);
  my @new;
  for my $i (1 .. $n/2) { 
    for my $x (unpack "L*", $a[$i]) {
      for my $y (unpack "L*", $a[$n - $i]) {
        for ($x + $y, $x * $y) { 
          next if vec($v, $_, 1);
          push @new, $_;
          vec($v, $_, 1) = 1;
          $min = $_ if $min > $_;
          $max = $_ if $max < $_;
        }
      }
    }
  } 
  $a[$n] = pack "L*", @new;
  printf "%s: min %s%s, max %s, new %s\n",
      $n, $min, isprime($min) ? '' : ' (c)', $max, 0+ at new;
  $prev = $max;
}