cp's OEIS Frontend

A067133 n is a term if the phi(n) numbers in [0,n-1] and coprime to n form an arithmetic progression.

%I A067133 #27 Sep 20 2024 02:06:14
%S A067133 1,2,3,4,5,6,7,8,11,13,16,17,19,23,29,31,32,37,41,43,47,53,59,61,64,
%T A067133 67,71,73,79,83,89,97,101,103,107,109,113,127,128,131,137,139,149,151,
%U A067133 157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241
%N A067133 n is a term if the phi(n) numbers in [0,n-1] and coprime to n form an arithmetic progression.
%C A067133 The sequence consists of primes, powers of 2 and 6. Sketch of proof: Let k be the common difference of the arithmetic progression. If n is odd, then 1 and 2 are coprime to n, so k=1 and n is prime. If n==0 (mod 4), then n/2-1 and n/2+1 are coprime to n, so k=2 and n is a power of 2. If n==2 (mod 4), then n/2-2 and n/2+2 are coprime to n, so k divides 4 and n is either 2 or 6.
%C A067133 From _Bernard Schott_, Jan 08 2021: (Start)
%C A067133 This sequence is the answer to the 2nd problem, proposed by Romania, during the 32nd International Mathematical Olympiad in 1991 at Sigtuna (Sweden) (see the link IMO Compendium and reference Kuczma).
%C A067133 These phi(m) numbers coprimes to m form an arithmetic progression with at least 3 terms iff m = 5 or m >= 7. (End)
%D A067133 Marcin E. Kuczma, International Mathematical Olympiads, 1986-1999, The Mathematical Association of America, 2003, pages 6 and 61-62.
%H A067133 The IMO Compendium, <a href="https://imomath.com/othercomp/I/Imo1991.pdf">Problem 2</a>, 32nd IMO 1991.
%H A067133 <a href="/index/O#Olympiads">Index to sequences related to Olympiads</a>.
%e A067133 8 is a term as phi(8) = 4 and the coprime numbers 1,3,5,7 form an arithmetic progression. 17 is a member as phi(17) = 16 and the numbers 1 to 16 form an arithmetic progression.
%t A067133 rps[ n_ ] := Select[ Range[ 0, n-1 ], GCD[ #, n ]==1& ]; difs[ n_ ] := Drop[ n, 1 ]-Drop[ n, -1 ]; Select[ Range[ 1, 250 ], Length[ Union[ difs[ rps[ # ] ] ] ]<=1& ]
%o A067133 (PARI) isok(n) = {my(v = select(x->gcd(x, n)==1, [1..n]), dv = vector(#v-1, k, v[k+1] - v[k])); if (#dv, if (vecmin(dv) != vecmax(dv), return(0))); return(1)} \\ _Michel Marcus_, Jan 08 2021
%o A067133 (Python)
%o A067133 from sympy import primepi
%o A067133 def A067133(n):
%o A067133     def bisection(f,kmin=0,kmax=1):
%o A067133         while f(kmax) > kmax: kmax <<= 1
%o A067133         while kmax-kmin > 1:
%o A067133             kmid = kmax+kmin>>1
%o A067133             if f(kmid) <= kmid:
%o A067133                 kmax = kmid
%o A067133             else:
%o A067133                 kmin = kmid
%o A067133         return kmax
%o A067133     def f(x): return int(n+x-(x>5)+(0 if x<=1 else 1-primepi(x))-x.bit_length())
%o A067133     return bisection(f,n,n) # _Chai Wah Wu_, Sep 19 2024
%Y A067133 Equals A000040 U A000079 U {6}.
%Y A067133 Equals A174090 U {6}.
%K A067133 easy,nonn
%O A067133 1,2
%A A067133 _Amarnath Murthy_, Jan 09 2002
%E A067133 Edited by _Dean Hickerson_, Jan 15 2002