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,1

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.

Mathematica

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

Prog

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

Crossrefs

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

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

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

Sequence in context: A329150 A230606 A117289 * A328513 A318719 A106317

Adjacent sequences: A339814 A339815 A339816 * A339818 A339819 A339820

Keyword

nonn

Author

Antti Karttunen, Dec 19 2020

Status

approved