[seqfan] Re: Divisibility sequences in OEIS.

[franktaw at netscape.net]

Confining our attention to the positive integers, there is a fairly 
obvious one-to-one correspondence between divisibility sequences and 
arbitrary sequences.

Let a(n) be a divisibility sequence of positive integers, defined on 
the positive integers.  Clearly, a(n) must be divisible by lcm(d|n and 
d<n, a(d)); so let b(n) be a(n) divided by this lcm.  Obviously, any 
arbitrary choice of b(n) will correspond to a unique divisibility 
sequence.  (For actual computation, it suffices to look at lcm(prime 
p|n, a(n/p)) .)

Performing this operation on the Fibonacci numbers (a divisibility 
sequence) gives A061446.  There is considerable reference there to this 
operation on GCD-morphic sequences -- sequences where a(gcd(n,m)) = 
gcd(a(n), a(m)).  For these sequences we have a(n) = product(d|m, 
b(d)).  However, the operation is characteristic for divisibility 
sequences, not for this more restrictive case -- that is, every choice 
of the sequence b gives rise to a divisibility sequence, but many do 
not give rise to a GCD-morphic sequence.

An example of the reverse transformation is A007955, the product of the 
divisors of n, which is the result of taking b(n) = n.  This case is 
also GCD-morphic.

An extreme example of a non-GCD-morphic divisibility sequence is 
A061142, 2^bigomega(n).  This is the transform of b(1) = 1, b(n) = 2 
for n > 1 -- A040000.  (Using the alternate definition suggested by the 
GCD-morphic sequences, a(n) = product(d|n, b(d)) would give a(n) = 
A100577(n) = 2^(d(n)-1).  This is also not GCD-morphic.  It is 
necessarily a divisibility sequence, but this approach is not 
characteristic.)

Starting with the divisibility sequence phi(n) -- A000010 -- we get a 
sequence which starts out like A072211.  However, it diverges at 15, 
where we have b(n) = 2, while A072211(15) = 1.  In general, this 
sequence will diverge from A072211 for any odd square-free number.  If 
we take b(n) = A072211(n) except for n=8, b(8) = 1, the inverse 
transform gives us A002322, the maximum order of any unit modulo n.  
The exception here reflects the fact that powers of 2 that are 8 or 
more do not have primitive roots.

Franklin T. Adams-Watters