# [seqfan] Re: Divisibility sequences in OEIS.

franktaw at netscape.net franktaw at netscape.net
Thu Dec 17 01:51:39 CET 2009

```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.