[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.
Franklin T. Adams-Watters
More information about the SeqFan
mailing list