A053575 -id:A053575 - cp's OEIS frontend

A339974 Odd primes that do not occur as the greatest prime divisor of any such odd composite k for which the odd part of phi(k) divides k-1.

3, 7, 11, 19, 31, 37, 59, 61, 83, 103, 107, 131

Offset: 1

Antti Karttunen, Dec 27 2020

Odd primes that do not occur as the greatest prime divisor (A006530) of any of the terms of A339880.
Naive way of computing (essentially an exhaustive search): apply A000523 to the terms of A339973, select unique values, add +2, and take the corresponding prime.
Questions: Is this sequence finite? If infinite, are there still only a finite number of 4k+1 primes (A002144) like 37 and 61?
a(13) >= 149, if it exists.

			Prime 127 is NOT a member, because there exists a squarefree composite number 10697881195 = 5*29*53*97*113*127, for which A053575(10697881195) = A336466(10697881195) = 120393, which is a divisor of 10697881195-1. Note that 10697881195 is a term of A339880, but not that of A339870.

Cf. A000523, A002144, A006530, A053575, A336466, A339870, A339880, A339973.

Cf. also A339869.

A339875 Intersection of A137409 and A339870: Composite numbers k of the form 4u+1 having more than one prime factor of type 4u+3, and for which the odd part of phi(k) divides k-1.

Original entry on oeis.org

561, 6601, 8481, 17733, 23001, 30889, 54741, 62745, 88561, 106141, 319965, 359601, 449065, 534061, 609301, 949785, 1357621, 2162721, 2288661, 2615977, 3284281, 4005001, 4698001, 4830805, 5381265, 6313681, 6594721, 6840001, 8093701, 11782005, 11921001, 14665105, 14892153, 15217741, 16577785, 19683001, 20154061, 20441701

Offset: 1

Antti Karttunen, Dec 26 2020

nonn

Composite numbers k of the form 4u+1 for which the odd part of phi(k) divides k-1 and for which A065338(k) > 1.

All terms k are squarefree and the 3-adic valuation of A065338(k) is a nonzero even number.

Intersection of A137409 and A339870.

Cf. A000010, A000265, A053575, A065338.

A065338(n) = { my(f = factor(n)); for (i=1, #f~, f[i, 1] = (f[i, 1]%4)); factorback(f); };
isA137409(n) = ((1==n)||(A065338(n)>1)); \\ Antti Karttunen, Dec 26 2020
A000265(n) = (n>>valuation(n, 2));
isA339870(n) = ((n>1)&&!isprime(n)&&(1==(n%4))&&!((n-1)%A000265(eulerphi(n))));
isA339875(n) = (isA137409(n)&&isA339870(n));

A339972 Odd part of phi(A019565(8*n)).

Original entry on oeis.org

1, 3, 5, 15, 3, 9, 15, 45, 1, 3, 5, 15, 3, 9, 15, 45, 9, 27, 45, 135, 27, 81, 135, 405, 9, 27, 45, 135, 27, 81, 135, 405, 11, 33, 55, 165, 33, 99, 165, 495, 11, 33, 55, 165, 33, 99, 165, 495, 99, 297, 495, 1485, 297, 891, 1485, 4455, 99, 297, 495, 1485, 297, 891, 1485, 4455, 7, 21, 35, 105, 21, 63, 105, 315, 7, 21

Offset: 0

Antti Karttunen, Dec 26 2020

Compare also to the scatter plots of A339898 and A339901.

Antti Karttunen, Table of n, a(n) for n = 0..16383

Quadrisection of A339971.

Cf. A000265, A019565, A057023, A053575, A339821, A339898, A339901.

A000265(n) = (n>>valuation(n, 2));
A339972(n) = { my(m=1, p=5); while(n>0, p = nextprime(1+p); if(n%2, m *= A000265(p-1)); n >>= 1); (m); };

If 16n = 2^e1 + 2^e2 + ... + 2^ek [e1 ... ek distinct], then a(n) = A057023(e1) * A057023(e2) * ... * A057023(ek).

a(n) = A339971(4*n) = A000265(A339821(4*n)) = A053575(A019565(8*n)).

A193417 Numbers n such that the number of the odd divisors of phi(n) is different from the number of the odd divisors of lambda(n).

Original entry on oeis.org

63, 91, 117, 126, 133, 171, 182, 189, 217, 234, 247, 252, 259, 266, 273, 275, 279, 301, 315, 333, 341, 342, 351, 364, 378, 387, 399, 403, 427, 434, 441, 451, 455, 468, 469, 481, 494, 504, 511, 513, 518, 532, 546, 549, 550, 553, 558, 559, 567, 585, 589, 602

Offset: 1

Michel Lagneau, Jul 26 2011

nonn

n such that A193453(n) is different of A193169(n).
Numbers n such that A000265(lambda(n)) < A000265(phi(n)), where A000265(m) is the odd part (largest odd divisor) of m. - Amiram Eldar and Thomas Ordowski, Feb 04 2019
From Jianing Song, Oct 19 2021: (Start)
Let G = (Z/kZ)* be the multiplicative group of integers modulo k and G_2 be the Sylow 2-subgroup of G. Sequence lists k such that G/G_2 is not cyclic; equivalently, decompose G as a product of cyclic groups C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j, then k is a term if and only if m > 1 and k_{m-1} is not a power of 2.
Numbers k such that there exists an odd prime p such that the p-rank of G is greater than 1. (The rank of a finitely generated group rank(G) is defined to be the size of the minimal generating sets of G, and the p-rank of G is the rank of the Sylow p-subgroup of G.)
k is a term if and only if k satisfies at least one of the two conditions: (a) there exists an odd prime p such that k has two distinct prime factors congruent to 1 modulo p (for example 91 = 7 * 13, 7 == 13 == 1 (mod 3)); (b) there exists an odd prime p such that k has a prime factor congruent to 1 modulo p and that k is divisible by p^2 (for example 275 = 11 * 5^2, 11 == 1 (mod 5)). (End)

			63 is in the sequence because phi(63) = 36 with 3 odd divisors {1, 3, 9} and lambda(63) = 6 with only 2 odd divisors {1, 3}.

Jinyuan Wang, Table of n, a(n) for n = 1..10000

Cf. A000010, A000265, A002322, A053575.

f[n_] := Block[{d = Divisors[EulerPhi[n]]}, Count[OddQ[d], True]]; Table[f[n], {n, 500}]; g[n_] := Block[{e = Divisors[CarmichaelLambda[n]]}, Count[OddQ[e], True]]; Table[g[n], {n, 500}]; a={};Do[If[ f[n] != g[n], AppendTo[a,n]], {n, 500}];a

is(n) = my(cp = eulerphi(n), cn=cp>>valuation(cp,2), cl=lcm(znstar(n)[2])); cl = cl >> valuation(cl, 2); numdiv(cl) != numdiv(cn) \\ David A. Corneth, Feb 18 2019

isA193417(n) = my(v=znstar(n)[2]); (#v<=1) || (v[2]==1<Jianing Song, Oct 19 2021

A303643 Numbers k such that k and phi(k) are in A292544.

Original entry on oeis.org

1, 1664, 6815744, 10092544, 27917287424, 4707284156416, 5506148073472, 7060926234624, 8259222110208, 114349209288704, 108649341010313216, 468374361246531584, 1918461383665793368064, 7858017827495089635590144, 11635911013790805806546944, 183907840308875463202177024

Offset: 1

Max Alekseyev and Altug Alkan, Apr 27 2018

nonn

			1 is in A292544, and eulerphi(1)=1, so 1 is a term.
1664 and 768=eulerphi(1668) are both in A292544, so 1664 is a term.

Cf. A007733, A053575, A066781, A292544.

isA292544(n) = Mod(2, n)^eulerphi(n)==eulerphi(n);
isok(n) = isA292544(n) && isA292544(eulerphi(n));

{ ZK(m) = my(z,k); z=znorder(Mod(2,m)); k=znlog(eulerphi(m),Mod(2,m)); if(type(k)!="t_INT",return()); [z,k]; }
{ getpowerof2(m) = my(m2,t,zk,zk2,r);
    m2 = eulerphi(m);
    t = valuation(m2,2);
    m2 \= 2^t;
    if( m2==1, return(0));
    zk=ZK(m);
    zk2=ZK(m2);
    if(!zk || !zk2, return());
    r = [zk[1],zk2[1],zk[2]-t-zk2[2]+1];  \\ solving r[1] * i = r[2] * j + r[3]
    r /= content(r);
    if( gcd(r[1],r[2])>1, return());
    ((r[2]*lift(Mod(-r[3]/r[2],r[1])) + r[3])/r[1] + r[2]*x)*zk[1] - zk[2] + 1;} \\ getpowerof2(m) returns z*i - k + 1 with x parameter (see formula section), i.e., getpowerof2(13) returns 12*x+7, that is, 13*2^(12*x+7) is a term for all x >= 0.

Following steps can be used in order to produce terms of this sequence.
(1) Take odd m, find z and k (see formula section of A292544).
(2) Represent phi(m) = 2^t*m', where m' is odd (i.e., m' = A053575(m)).
(3) For this m', find z' and k'.
(4) Solve z*i - k + t = z'*j - k' + 1 for positive i, j.
(5) Each such solution gives a term m*2^(z*i - k + 1) of this sequence.
For all x >= 0, 13*2^(12*x+7), 77*2^(60*x+17), 137*2^(136*x+35), 173*2^(1204*x+259), 193*2^(96*x+49), 269*2^(8844*x+6567), 411*2^(136*x+34), 519*2^(1204*x+258), 557*2^(38364*x+28635), 563*2^(19670*x+9836), 581*2^(2460*x+789), 641*2^(64*x+33), 653*2^(52812*x+39447), 667*2^(4620*x+3405), 769*2^(384*x+193), 807*2^(8844*x+6566) are terms of this sequence (m < 10^3 where m*2^(z*i - k + 1) is the corresponding form).

A334070 Number of even-order elements in the multiplicative group of integers modulo n.

Original entry on oeis.org

0, 0, 1, 1, 3, 1, 3, 3, 3, 3, 5, 3, 9, 3, 7, 7, 15, 3, 9, 7, 9, 5, 11, 7, 15, 9, 9, 9, 21, 7, 15, 15, 15, 15, 21, 9, 27, 9, 21, 15, 35, 9, 21, 15, 21, 11, 23, 15, 21, 15, 31, 21, 39, 9, 35, 21, 27, 21, 29, 15, 45, 15, 27, 31, 45, 15, 33, 31, 33, 21, 35, 21, 63

Offset: 1

Robert A. Jones, Apr 13 2020

nonn

The number of even-order elements in a finite abelian group G is |G| - b(|G|), where b is given by A000265. To see this, decompose G as a product of cyclic groups of orders {m_k}. G has [prod_k b(m_k)] elements of odd order, since an element has odd order if and only if all its components have odd order, and each C_m factor has b(m) elements of odd order. Since b can be pulled outside the product, G has b(|G|) elements of odd order. Using that the order of (Z/nZ)^x is phi(n), we obtain a(n) = phi(n) - b(phi(n)).

Since phi(n) is even when n > 2, a(n) is odd when n > 2.

			For n = 10, the elements of (Z_n)^x with even order are 3 (order 4), 7 (order 4), and 9 (order 2). Thus, a(10) = 3.

Cf. A000010, A053575, A129527, A331739 (number of even-order elements in Z_n).

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

a[n_] := Length@
  Select[Range[n] - 1, EvenQ[MultiplicativeOrder[#, n]] &];
oddPart[n_] := n/2^IntegerExponent[n,2];
a[n_] := EulerPhi[n] - oddPart[EulerPhi[n]];

a(n) = A000010(n) - A053575(n) = A331739(A000010(n)).

cp's OEIS Frontend

A339974 Odd primes that do not occur as the greatest prime divisor of any such odd composite k for which the odd part of phi(k) divides k-1.

Views

Author

Keywords

Comments

Examples

Crossrefs

A339875 Intersection of A137409 and A339870: Composite numbers k of the form 4u+1 having more than one prime factor of type 4u+3, and for which the odd part of phi(k) divides k-1.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A339972 Odd part of phi(A019565(8*n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A193417 Numbers n such that the number of the odd divisors of phi(n) is different from the number of the odd divisors of lambda(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A303643 Numbers k such that k and phi(k) are in A292544.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

PARI

Formula

A334070 Number of even-order elements in the multiplicative group of integers modulo n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula