Math Questions: A096216 & A116537

[hv at crypt.org]

Leroy Quet <qq-quet at mindspring.com> wrote:
:Regarding 2 related sequences:
:
:Sequence A096216 is (paraphrasing the official name of the sequence):
:a(1)=1, a(n) = the number of earlier terms of the sequence which are 
:coprime to n.
:
:While sequence A116537 is (again paraphrasing):
:a(1)=1, a(n) = the number positive integers which are coprime to n, are 
:<= n, and do _not_ occur among the earlier terms of the sequence.
:
:
:First, is A096216 such that a(2n) is always <= to both a(2n+1) and 
:a(2n-1)?
:
:(Calculating a few more terms of the sequence A116537, however, shows an 
:exception to the strict zig-zaggedness of that sequence.) 
:
:Also, it SEEMS like the limits, where {a(k)} is either sequence,
:
:(1/n^2) * sum{k=1 to n} a(k), as n -> inf,
:
:approaches one of two nonzero finite constants, the constant depending on 
:which sequence is {a(k)}.
:(I base my conjecture that the two limits are nonzero finite constants 
:based solely upon the behavior of the limits for n = 20. Could someone 
:test this for, say, n = 1000 or higher?)

I don't know how to test it, but here's some code that generates A096216
pretty quickly:

#!/usr/bin/perl -w
use bigint;  # only because it's an easy way to get gcd()
$| = $n = 1;
@a = (0);
while (1) {
  $v = grep $n->bgcd($_) == 1, @a;
  print $a[$n++] = $v, " ";
}
__END__

and for A116537:

#!/usr/bin/perl -w
use Math::Pari qw/ gcd eulerphi /;
$| = 1;
$n = 2;
%seen = (1 => 1);
while (1) {
  $v = eulerphi($n) - grep gcd($n, $_) == 1, keys %seen;
  $seen{$v} = 1;
  ++$n;
  print "$v ";
}

I notice the latter needs more terms; I'll send njas as many of these as fit:
1 0 1 1 3 1 4 2 3 2 6 3 7 4 4 5 9 3 10 4 7 5 13 4 12 7 11 6 16 4 17 8 10 9 12
6 21 9 14 8 23 6 24 11 13 13 27 9 25 10 19 12 30 9 22 13 21 15 33 9 34 15 21
17 27 12 39 17 28 13 41 14 42 19 24 20 36 15 45 18 34 23 47 14 37 22 34 22 51
14 41 24 38 26 41 20 56 23 37 23 59 20 60 28 30 30 63 23 64 23 46 28 66 24 51

If you don't have access to perl or some other mechanism to generate these,
let me know and I can mail you a few thousand terms of each. (Note that
A096216 also shows formulae for Maple and Mathematica, which should be
possible to adapt also for A116537.)

Hugo