A339879 -id:A339879 - cp's OEIS frontend

A053575 Odd part of phi(n): a(n) = A000265(A000010(n)).

1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 5, 1, 3, 3, 1, 1, 1, 3, 9, 1, 3, 5, 11, 1, 5, 3, 9, 3, 7, 1, 15, 1, 5, 1, 3, 3, 9, 9, 3, 1, 5, 3, 21, 5, 3, 11, 23, 1, 21, 5, 1, 3, 13, 9, 5, 3, 9, 7, 29, 1, 15, 15, 9, 1, 3, 5, 33, 1, 11, 3, 35, 3, 9, 9, 5, 9, 15, 3, 39, 1, 27, 5, 41, 3, 1, 21, 7, 5, 11, 3, 9, 11, 15, 23

Offset: 1

Labos Elemer, Jan 18 2000

This is not necessarily the squarefree kernel. E.g., for n=19, phi(19)=18 is divisible by 9, an odd square. Values at which this kernel is 1 correspond to A003401 (polygons constructible with ruler and compass).

Multiplicative with a(2^e) = 1, a(p^e) = p^(e-1)*A000265(p-1). - Christian G. Bower, May 16 2005

			n = 70 = 2*5*7, phi(70) = 24 = 8*3, so the odd kernel of phi(70) is a(70)=3. [corrected by _Bob Selcoe_, Aug 22 2017]
From _Bob Selcoe_, Aug 22 2017: (Start)
a(89) = 88/8 = 11.
For n = 8820, 8820 = 2^2*3^2*5*7^2; S = 3*5*7 = 105, n" = 3^2*5*7^2 = 2205. a(3)*a(5)*a(7) = 1*1*3 = 3; a(8820) = 3*2205/105 = 63.
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A000010, A000265, A227944, A329697, A336466, A336468, A336469, A339879, A339971, A339974.

a053575 = a000265 . a000010  -- Reinhard Zumkeller, Oct 09 2013

a:= n-> (t-> t/2^padic[ordp](t, 2))(numtheory[phi](n)):
seq(a(n), n=1..80);  # Alois P. Heinz, Apr 14 2020

Array[NestWhile[Ceiling[#/2] &, EulerPhi@ #, EvenQ] &, 94] (* Michael De Vlieger, Aug 22 2017 *) (* or *)
t=Array[EulerPhi,94]; t/2^IntegerExponent[t,2] (* Giovanni Resta, Aug 23 2017 *)

a(n)=n=eulerphi(n);n>>valuation(n,2) \\ Charles R Greathouse IV, Mar 05 2013

From Bob Selcoe, Aug 22 2017: (Start)
Let n" be the odd part of n, S be the odd squarefree kernel of n and p_i {i = 1..z} be all the prime factors of S. Then the sequence can be constructed by the following:
a(1) = 1;
a(n) = (n-1)" when n is prime; and
a(n) = Product_{i = 1..z} a(p_i)*n"/S when n is composite (see Examples).
(End)
From Antti Karttunen, Dec 27 2020: (Start)
a(n) = A336466(n) for squarefree n (see A005117).
A336466(a(n)) = A336468(n), A329697(a(n)) = A336469(n) = A329697(n) - A005087(n).
(End)

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

Original entry on oeis.org

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)));

A339880 Odd composite numbers k such that A053575(k) [the odd part of phi] divides k-1.

Original entry on oeis.org

15, 51, 85, 91, 255, 435, 451, 561, 595, 771, 1105, 1261, 1285, 1351, 1695, 2091, 2431, 2465, 3655, 3855, 4369, 4795, 5083, 5151, 5383, 6601, 6643, 6735, 7051, 8245, 8481, 8695, 8911, 8995, 9061, 9605, 10585, 11155, 13107, 15051, 15211, 16405, 16705, 17733, 18721, 19669, 20451, 21845, 22359, 23001, 26335, 28645

Offset: 1

Antti Karttunen, Dec 24 2020

nonn

No common terms with A016105. See A339870 for the reason. - Antti Karttunen, Dec 26 2020

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

Cf. A000010, A000265, A016105, A053575.
Subsequence of A005117 and of A339879, and of A340077.
Cf. A339869, A339870 (subsequences).
Cf. also A002997, A053576, A339817.

A000265(n) = (n>>valuation(n, 2));
isA339880(n) = (bitand(n,1)&&(n>1)&&!isprime(n)&&!((n-1)%A000265(eulerphi(n))));

A340077 Odd numbers k for which k-1 is a multiple of A053575(k) [the odd part of phi(k)].

Original entry on oeis.org

1, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71, 73, 79, 83, 85, 89, 91, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 255, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313

Offset: 1

Antti Karttunen, Dec 29 2020

nonn

Sequence A003961(A340076(i)), i = 1.., sorted into ascending order. In other words, this sequence consists of such odd numbers k that A064989(k) is in A340076.

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

Cf. A064989, A340075, A340076.
Subsequence of A339879.
Subsequences: A065091, A339880 (composite terms), A339869, A339870 (and their further subsequences).

A000265(n) = (n>>valuation(n, 2));
isA340077(n) = ((n%2)&&!((n-1)%A000265(eulerphi(n))));

A064989(n) = { my(f=factor(n)); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f) };
isA340077(n) = ((n%2)&&(1==A340075(A064989(n)))); \\ Needs also code from A340075.

cp's OEIS Frontend

A053575 Odd part of phi(n): a(n) = A000265(A000010(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

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

A339880 Odd composite numbers k such that A053575(k) [the odd part of phi] divides k-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A340077 Odd numbers k for which k-1 is a multiple of A053575(k) [the odd part of phi(k)].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI