A339907 -id:A339907 - 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.

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

Antti Karttunen, Dec 19 2020

nonn

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)

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.

Cf. A000010, A002144, A002145, A007814, A016105, A016813, A091113, A339816.
Cf. A000040, A016105, A339818, A339819 (subsequences).
Cf. also A339879, A339907, A339869, A339870, A339880.

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

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

A339908 Odd squarefree numbers k > 1 for which bigomega(phi(k)) < bigomega(k-1), where bigomega gives the number of prime divisors, counted with multiplicity.

Original entry on oeis.org

33, 65, 129, 141, 145, 161, 177, 201, 217, 249, 253, 321, 385, 393, 417, 501, 537, 649, 681, 705, 721, 737, 849, 865, 897, 913, 973, 993, 1041, 1057, 1081, 1101, 1121, 1135, 1149, 1169, 1177, 1281, 1329, 1345, 1401, 1441, 1457, 1473, 1497, 1509, 1537, 1561, 1569, 1585, 1633, 1689, 1729, 1761, 1793, 1821, 1837, 1841

Offset: 1

Antti Karttunen, Dec 21 2020

nonn

All terms can be found in A339911. Also, all nonmultiples of 3 certainly occur in A339912 also.

The first term of the form 4u+3 is 1135.

Antti Karttunen, Table of n, a(n) for n = 1..26693; all terms < 2^20

Cf. A000010, A001222.
Subsequence of A056911 and of A339907, A339911.
Cf. also A339912.
Cf. A339909 (a subsequence).

isA339908(n) = ((n>1)&&(n%2)&&issquarefree(n)&&(bigomega(eulerphi(n))

A339906 Numbers k for which A339812(2k) >= A339902(k).

Original entry on oeis.org

1, 2, 4, 5, 8, 9, 10, 14, 16, 18, 32, 64, 65, 72, 84, 128, 129, 132, 136, 141, 145, 170, 256, 258, 261, 385, 448, 512, 516, 578, 642, 912, 1024, 1040, 1049, 1160, 1352, 2048, 4096, 4097, 4100, 4111, 4160, 4652, 4675, 4864, 5124, 5280, 8192, 8193, 8194, 8195, 8196, 8200, 8214, 8216, 8258, 8320, 8329, 8468, 8704

Offset: 1

Antti Karttunen, Dec 21 2020

nonn

Terms of (1/2)*A048675(A339907(i)), for i >= 1, sorted into ascending order.
The first term not present in A339816 is 10, the second is 642; the first term of A339816 not present here is 12, the second is 21.
First terms with binary weights (A000120) w = 1..9 are: 1, 5, 14, 141, 4111, 25676, 41674, 1094530, 423297.

			10 ("1010" in binary) is present, because it encodes an odd squarefree number 5*11, for which phi(55) = 4*10 = 40, and bigomega(55-1) = 4 >= 4 = bigomega(40).
12 ("1100" in binary) is NOT present, because it encodes an odd squarefree number 7*11, for which phi(77) = 6*10 = 60, and bigomega(77-1) = 3 < 4 = bigomega(60).

Antti Karttunen, Table of n, a(n) for n = 1..514

Cf. A000010, A001222, A019565, A048675, A339812, A339902, A339907.
Cf. A000079 (a subsequence).
Cf. also A339816.

A019565(n) = { my(m=1, p=1); while(n>0, p = nextprime(1+p); if(n%2, m *= p); n >>= 1); (m); };
A339812(n) = bigomega(A019565(n)-1);
A339902(n) = { my(s=0, p=2); while(n>0, p = nextprime(1+p); if(n%2, s += bigomega(p-1)); n >>= 1); (s); };
isA339906(n) = (A339812(2*n) >= A339902(n));

A019565(n) = { my(m=1, p=1); while(n>0, p = nextprime(1+p); if(n%2, m *= p); n >>= 1); (m); };
isA339906(n) = { my(x=A019565(2*n)); (bigomega(eulerphi(x))<=bigomega(x-1)); };

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A339908 Odd squarefree numbers k > 1 for which bigomega(phi(k)) < bigomega(k-1), where bigomega gives the number of prime divisors, counted with multiplicity.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A339906 Numbers k for which A339812(2k) >= A339902(k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI