cp's OEIS Frontend

Consider the function f(n) = the number of positive integers k < n such that k^n (mod n) == 1. This sequence lists the values of n at which f(n) reaches a new maximum.

All powers of two are present except its square. f(2^n) (with exception noted) = 2^(n-1) = 2^n/2.

All powers of two multiplied by 100, 1000 and 100000, but not 10000, are also present.

Terms other than the above are 27, 54, 243, 486, 500, 972, 1944, 3888, 4624, 7776, 9248, 12100, 12500, 15552, 18496, 24200, 25000, 31104, 36992, 48400, 50000, ..., .

Conjecture: f(x)/x -> 5/12.

Coincides with A072995 for many terms, but differs, e.g., in n = 20, 40, 52, ... in addition to the zeros in A072995. See also the comments in A072994. - M. F. Hasler, Feb 23 2014

a(n) <= n^2. - Robert G. Wilson v, Feb 27 2014

A072989 lists the indices for which a(n) differs from A050399(n), e.g., in n = 20, 40, 52, ... in addition to the zeros in this sequence (n = 30, 42, 66, 70, 78, 90, ...). See also A009195 vs. A072994. [Corrected and extended by M. F. Hasler, Feb 23 2014]

The sequence seems difficult to extend, as the next term a(30) is larger than 5100. However, a(32)=64, a(64)=128 and a(128)=256 can be easily calculated. It thus appears that a(2^k)=2^(k+1), for k=1,2,3,.... Is this known to be true? - John W. Layman, Aug 05 2003 -- Answer: It's true. One could have defined the sequence so that a(1)=2: then it would be true for 2^0 also. - Don Reble, Feb 23 2014

a(30), if it exists, is greater than 400000. - Ryan Propper, Sep 10 2005

a(30) doesn't exist: If N is even, and divisible by D different odd primes, but not divisible by 2^D, then a(N) doesn't exist. - Don Reble, Feb 23 2014 [This and the preceding comment refer to the former definition lacking the clause "0 if no such k exists". - Ed.]

Conjecture: a(n)=0 iff n/2 is in A061346. - Robert G. Wilson v, Feb 23 2014

[n=420 seems to be a counterexample to the above conjecture. - M. F. Hasler, Feb 24 2014]

From Robert G. Wilson v, Mar 05 2014: (Start)

Observation:

If n = 1 then a(n) = 1 by definition;

If, but not iff, n (an even number) is a member of A238367 then a(n) = 0;

If n (an even number not in A238367) is {684, 954, ...}, then a(n) = 0;

If n (an odd number) is {273, 399, 651, 741, 777, 903, ...}, then a(n) = 0;

If p is a prime [A000040] and e is its exponent, then a(p^e) = p^(e+1);

If p is a prime then a(2p^e) = 2p^(e+1);

If p is a prime then a(n) # p since the f(p)=1.

(End)

Often A072995(n) equals A050399(n). They differ at n: 20, 30, 40, 42, 52, 60, 66, 68, 70, 78, 80, 84, 90, 100, 102, 104, 110, 114, 116, 120, 126, 130, 132, ... - Robert G. Wilson v, Dec 06 2014

When A072995(n)>0 and does not equal A050399(n): 20, 40, 52, 60, 68, 80, 84, 100, 104, 116, 120, 132, 136, 140, 148, 156, 160, 164, 168, 171, 180, 200, ... - Robert G. Wilson v, Dec 06 2014

When a(n) > 1, then 2n <= a(n) <= n^2. - Robert G. Wilson v, Dec 10 2014

a(n) = 1 if n is of the form 2^p and a(n) = n-1 if n prime.

Conjecture: limit of a(n)/n is zero.

This conjecture is certainly wrong as stated, because sequences "Numbers such that..." have lim a(n)/n >= 1 and a(n) > n for all indices following the first one for which this holds, as here: a(1) > 1. - M. F. Hasler, Feb 24 2014