cp's OEIS Frontend

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

%I A339817 #31 Feb 18 2021 00:49:56
%S A339817 2,3,5,7,11,13,17,19,21,23,29,31,33,37,41,43,47,53,57,59,61,65,67,69,
%T A339817 71,73,77,79,83,89,93,97,101,103,107,109,113,127,129,131,133,137,139,
%U A339817 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
%N A339817 Squarefree numbers k > 1 for which the 2-adic valuation of phi(k) does not exceed the 2-adic valuation of k-1.
%C A339817 After 2, terms of A003961(A019565(A339816(i))) [or equally, of A019565(2*A339816(i))], for i = 1.., sorted into ascending order.
%C A339817 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).
%C A339817 From _Antti Karttunen_, Dec 22-26 2020: (Start)
%C A339817 Composite terms in this sequence are all of the form 4u+1 (A016813, A091113).
%C A339817 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.
%C A339817 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.
%C A339817 (End)
%H A339817 Antti Karttunen, <a href="/A339817/b339817.txt">Table of n, a(n) for n = 1..21695</a>
%H A339817 D. H. Lehmer, <a href="http://dx.doi.org/10.1090/s0002-9904-1932-05521-5">On Euler's totient function</a>, Bulletin of the American Mathematical Society, 38 (1932), 745-751.
%H A339817 Wikipedia, <a href="https://en.wikipedia.org/wiki/Lehmer&#39;s_totient_problem">Lehmer's totient problem</a>.
%t A339817 Select[Range[2, 250], SquareFreeQ[#] && IntegerExponent[EulerPhi[#], 2] <= IntegerExponent[# - 1, 2] &] (* _Amiram Eldar_, Feb 17 2021 *)
%o A339817 (PARI) isA339817(n) = ((n>1)&&issquarefree(n)&&(valuation(eulerphi(n),2)<=valuation(n-1,2)));
%Y A339817 Cf. A000010, A002144, A002145, A007814, A016105, A016813, A091113, A339816.
%Y A339817 Cf. A000040, A016105, A339818, A339819 (subsequences).
%Y A339817 Cf. also A339879, A339907, A339869, A339870, A339880.
%K A339817 nonn
%O A339817 1,1
%A A339817 _Antti Karttunen_, Dec 19 2020