login
A339817
Squarefree numbers k > 1 for which the 2-adic valuation of phi(k) does not exceed the 2-adic valuation of k-1.
12
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
D. H. Lehmer, On Euler's totient function, Bulletin of the American Mathematical Society, 38 (1932), 745-751.
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)));
KEYWORD
nonn
AUTHOR
Antti Karttunen, Dec 19 2020
STATUS
approved