A339817 Squarefree numbers k > 1 for which the 2-adic valuation of phi(k) does not exceed the 2-adic valuation of k-1.

2, 3, 5, 7, 11, 13, 17, 19, 21, 23, 29, 31, 33, 37, 41, 43, 47, 53, 57, 59, 61, 65, 67, 69, 71, 73, 77, 79, 83, 89, 93, 97, 101, 103, 107, 109, 113, 127, 129, 131, 133, 137, 139, 141, 145, 149, 151, 157, 161, 163, 167, 173, 177, 179, 181, 191, 193, 197, 199, 201, 209, 211, 213, 217, 223, 227, 229, 233, 237, 239, 241

Offset: 1

Author

Antti Karttunen, Dec 19 2020

Keywords

• nonn

Comments

After 2, terms of A003961(A019565(A339816(i))) [or equally, of A019565(2*A339816(i))], for i = 1.., sorted into ascending order.

Natural numbers n that satisfy equation y * phi(n) = n - 1 (with y an integer) all occur in this sequence. Lehmer conjectured that there are no solutions such that n is composite (and thus y > 1).

From Antti Karttunen, Dec 22-26 2020: (Start)

Composite terms in this sequence are all of the form 4u+1 (A016813, A091113).

Generally, if any term k > 2 here has x prime divisors (which are all odd and distinct, i.e., A001221(k) = A001222(k) = x), then k is of the form 2^x * u + 1 (where u maybe even or odd), because each prime divisor of k contributes at least one instance of 2 in phi(k). Specifically, each prime factor of the form 4u+3 (A002145) contributes one instance of 2 (+1 to the 2-adic valuation), while primes of the form 4u+1 (A002144) contribute at least +2 to the 2-adic valuation. There must be an even number of 4u+3 primes, as otherwise the product would be of the form 4u+3. On the other hand, although all the terms of A016105 occur here, none of them occurs in A339870.

If the only terms this sequence shares with A339879 are the primes (A000040), then Lehmer's conjecture certainly holds. Similarly if the sequences A339818 and A339869 do not have any common terms.

(End)

Links

• Antti Karttunen, Table of n, a(n) for n = 1..21695
• D. H. Lehmer, On Euler's totient function, Bulletin of the American Mathematical Society, 38 (1932), 745-751.
• Wikipedia, Lehmer's totient problem.

Crossrefs

Cf. A000010, A002144, A002145, A007814, A016105, A016813, A091113, A339816.

Cf. A000040, A016105, A339818, A339819 (subsequences).

Cf. also A339879, A339907, A339869, A339870, A339880.

Programs

Mathematica

Select[Range[2, 250], SquareFreeQ[#] && IntegerExponent[EulerPhi[#], 2] <= IntegerExponent[# - 1, 2] &] (* Amiram Eldar, Feb 17 2021 *)

PARI

isA339817(n) = ((n>1)&&issquarefree(n)&&(valuation(eulerphi(n),2)<=valuation(n-1,2)));