[seqfan] Re: A046790, A046791 obscure, need clarification
Don Reble
djr at nk.ca
Mon Jun 6 09:40:37 CEST 2016
> A046790 and A046791 from 1999 could use some clarification.
> %K A046790 nonn,uned,obsc
A046790 may have begun in obscurity, but now we have three helpful
definitions in the comments,
D1: Numbers n such that A008475(n) is different from A001414(n).
- Benoit Cloitre, Jan 11 2003
D2: moduli n for which there exist affine maps f:x->a*x + b modulo n,
with a>1, such that f has order n in the affine group.
- Emmanuel Amiot, Jul 28 2007
D3: Numbers n such that A005361(n)/A003557(n) < 1. - Anthony Browne,
Jun 03 2016
a proposed definition from njas,
D4: numbers i such that there is a smaller positive number j such that
(i+j)/2 and sqrt(i*j) are integers (I inserted "positive".)
and if I may join the chorus du jour,
D5: positive numbers divisible by 8 or by the square of an odd prime.
Let S1,...,S5 be the integer sets defined by D1,...,D5.
Definitions:
- component of n: for any prime p, the highest power of p which divides n.
- big component: any composite component, except 4
The point of a big component p^k, is that p^k > p*k, while for other
components, p^1 = p*1, and 2^2 = 2*2. Also, D5 can be written,
"Positive numbers with a big component."
--- S1 ---
A008475 maps n = product(p^k) to a(n) = sum(p^k).
A001414 sums the prime factors of n (including repetitions);
a(n) = sum(p*k).
If sum(p^k) isn't sum(p*k), then for some component, p^k isn't p*k,
so p^k is a big component.
S1 is a subset of S5.
If n has a big component, that component makes A008475 bigger than
A001414.
S5 is a subset of S1.
--- S2 ---
Using Knuth's theorem A, [TAOCP volume 2, second edition,
section 3.2.1.2, p16], we see that there is such an affine map
f:x->a*x + b modulo n, iff
- each prime dividing n also divides a-1, and
- if 4 divides n, then 4 also divides a-1.
(Also, b must be coprime to n; b=1 suffices.)
We may take a to be within [2,n-1].
(a=1 works, but it's forbidden: "with a>1".)
If n is square-free, then n divides a-1: all a-values in [2,n-1]
fail, and there is no such map.
So n is not square-free. If the only composite component of n is 4,
then again n divides a-1.
Therefore n is divisible by 8 or by the square of an odd prime.
S2 is a subset of S5.
If n is divisible by 8, let d be the highest odd factor of n,
let a=4d+1. 1 < a=4d+1 < 8d <= n.
If n is divisible by odd p^2, let a=(n/p)+1.
1 <= n/(p^2) < a=(n/p)+1 < n.
Either way, Knuth's theorem shows that there is a suitable affine
map using that a-value.
S5 is a subset of S2.
--- S3 ---
Dr. Brown could simply write A005361(n) < A003557(n), since both
sequences are positive.
A005361 has the product of the exponents in n = product(p^k).
A003557 has n divided by its largest square-free divisor.
If n is square-free, than A003557(n) = 1 = A005361(n).
If n is 4 times an odd square-free number, then
A003557(n) = 2 = A005361(n).
So if A003557(n) > A005361(n), n must be divisible by 8 or by the
square of an odd prime.
S3 is a subset of S5.
First, show that A005361(n) <= A003557(n) always.
Let n = product(p^k); then A005361(n) = product(k),
A003557(n) = product(p^(k-1)).
If p^k is a big component, then p^k > p*k, and p^(k-1) > k.
If p^k is not big, then p^k = p*k, and p^(k-1) = k.
Each factor of A003557 is >= the corresponding factor of A005361,
so the product is >=.
Let n be a element of S5; let c=p^k be a big component of n.
Then p*A005361(n) = p*k*A005361(n/c) <= p*k*A003557(n/c)
< (p^k)*A003557(n/c) = p*(c/p)*A003557(n/c) = p*A003557(n).
Therefore A005361(n) < A003557(n) and n is in S3.
S5 is a subset of S3.
--- S4 ---
If i is divisible by 8, then let j=i/4; if i is divisible by an odd p^2,
let j=i/(p^2). Then 0<j<i, and (i+j)/2 and sqrt(ij) are integers.
S5 is a subset of S4.
Let i, an element of S4, equal (a^2)*b, where b is square-free.
If (i*j) is a square, then j=b*(c^2), for some value of c. D4 says
0<j<i; therefore 0<c<a and 1<a.
If a=2, then c=1, and (i+j)/2 = 5b/2: that is an integer,
so b is even, and 8 divides i.
If a is a higher power of two, then 8 divides i.
Otherwise a is divisible by an odd prime p, and p^2 divides i.
S4 is a subset of S5.
-----
Phew. If that's all right, then we have five good definitions of
A046790. I like D2, because of the connection with LCM pseudorandom
generators. For ease of computation, D5 is pretty good. (Yes, the
%STU values agree.) But D4 seems closest to the author's intent.
Maybe the sequence isn't "core", but it's surely "nice".
Thanks, David.
--
Don Reble djr at nk.ca
More information about the SeqFan
mailing list