[seqfan] Divisor congruences
franktaw at netscape.net
franktaw at netscape.net
Sat Oct 31 11:58:22 CET 2009
A related concept: let a(n) be the smallest number such that no two
divisors of n are congruent modulo a(n).
This sequence starts:
1,2,3,4,3,6,4,5,5,6,3,7,5,8,8,9,3,10,4,7,8,
6,3,13,7,7,5,11,3,11,4,9,7,6,8,13,5,5,7,
11,3,16,4,12,13,6,3,17,5,11,9,7,3,10,7,
15,5,5,3,21,7,7,11,11,7,14,4,7,7,16,3,13,
5,10,13,7,8,14,4,17,7,6,3,23,9,8,5,13,3,
19,8,12,8,6,8,17,5,9,13,13
I'm wondering about the asymptotic behavior of this sequence. For n >
6, we must have a(n) <= floor(n/2) + 1, but it appears that we can do
much better. (Equality appears to hold only for n in
1,2,5,7,8,9,10,12,14,15,16,18,24.) I suspect something can be done
looking at the C(tau(n),2) differences between divisors, but it isn't
obvious to me how to carry out this idea. Our a(n) must not only not
be a difference, it can't divide any of them.
Second question: does every integer > 2 occur infinitely often in this
sequence? Certainly a(p) = 3 for any prime p == 2 (mod 3), a(p) = 4
for p == 7 (mod 12), and a(p) = 5 for p == 13, 25, 37, or 49 (mod 60).
In general, any prime power can be obtained in this way -- take p == 1
(mod A003418(q^k-1)) but not == 1 (mod q^k).
The case a(n) = 6 is less trivial; it is obtained for a(2p) where p is
a prime == 5 (mod 6). I suspect that similar constructions can be
found for arbitrary target values. Up to n = 10000, the smallest value
not found is 54.
I have submitted this sequence as A167234.
Franklin T. Adams-Watters
-----Original Message-----
From: Andrew Weimholt <andrew.weimholt at gmail.com>
I am tentatively using the term "orderly numbers" to indicate numbers,
n,
for which there exists some number, k > tau(n), such that the set of
divisors of n is congruent to the set {1,2,...tau(n)} mod k.
...
More information about the SeqFan
mailing list