cp's OEIS Frontend

A072995 Least k > 0 such that the number of solutions to x^k == 1 (mod k) 1 <= x <= k is equal to n, or 0 if no such k exists.

%I A072995 #68 Feb 27 2020 20:36:55
%S A072995 1,4,9,8,25,18,49,16,27,50,121,36,169,98,225,32,289,54,361,110,147,
%T A072995 242,529,72,125,338,81,196,841,0,961,64,1089,578,1225,108,1369,722,
%U A072995 507,100,1681,0,1849,484,675,1058,2209,144,343,250,2601,1378,2809
%N A072995 Least k > 0 such that the number of solutions to x^k == 1 (mod k) 1 <= x <= k is equal to n, or 0 if no such k exists.
%C A072995 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]
%C A072995 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
%C A072995 a(30), if it exists, is greater than 400000. - _Ryan Propper_, Sep 10 2005
%C A072995 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.]
%C A072995 Conjecture: a(n)=0 iff n/2 is in A061346. - _Robert G. Wilson v_, Feb 23 2014
%C A072995 [n=420 seems to be a counterexample to the above conjecture. - _M. F. Hasler_, Feb 24 2014]
%C A072995 From _Robert G. Wilson v_, Mar 05 2014: (Start)
%C A072995 Observation:
%C A072995 If n = 1 then a(n) = 1 by definition;
%C A072995 If, but not iff, n (an even number) is a member of A238367 then a(n) = 0;
%C A072995 If n (an even number not in A238367) is {684, 954, ...}, then a(n) = 0;
%C A072995 If n (an odd number) is {273, 399, 651, 741, 777, 903, ...}, then a(n) = 0;
%C A072995 If p is a prime [A000040] and e is its exponent, then a(p^e) = p^(e+1);
%C A072995 If p is a prime then a(2p^e) = 2p^(e+1);
%C A072995 If p is a prime then a(n) # p since the f(p)=1.
%C A072995 (End)
%C A072995 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
%C A072995 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
%C A072995 When a(n) > 1, then 2n <= a(n) <= n^2. - _Robert G. Wilson v_, Dec 10 2014
%H A072995 Robert G. Wilson v, <a href="/A072995/b072995.txt">Table of n, a(n) for n = 1..1013</a> (first 200 terms from Don Reble)
%H A072995 Robert G. Wilson v, <a href="/A072995/a072995.pdf">Graph of n, a(n) for n = 1..1000</a>
%F A072995 First occurrence of n in A072994.
%t A072995 t = Table[0, {1000}]; f[n_] := (d = If[EvenQ@ n, 2, 1]; d*Length@ Select[ Range[ n/d], PowerMod[#, n, n] == 1 &]); f[1] = 1; k = 1; While[k < 520001, If[ PrimeQ@ k, k++]; a = f@ k; If[a < 1001 && t[[a]] == 0, t[[a]] = k; Print[{a, k}]]; k++]; t (* _Robert G. Wilson v_, Dec 12 2014 *)
%o A072995 (PARI) A072995(n)=(n%2||n%2^(omega(n)-1)==0)&&for(k=1,9e9,A072994(k)==n&&return(k)) \\ _M. F. Hasler_, Feb 23 2014
%Y A072995 Cf. A072994.
%K A072995 nonn
%O A072995 1,2
%A A072995 _Benoit Cloitre_, Aug 21 2002
%E A072995 More terms from _Don Reble_, Feb 23 2014
%E A072995 Edited, at the suggestion of _Don Reble_, by _M. F. Hasler_, Feb 23 2014