A336466 -id:A336466 - cp's OEIS frontend

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

85, 561, 1105, 1261, 1285, 2465, 4369, 6601, 8245, 8481, 9061, 9605, 10585, 16405, 16705, 17733, 18721, 19669, 21845, 23001, 28645, 30889, 38165, 42121, 43165, 46657, 54741, 56797, 57205, 62745, 65365, 74593, 78013, 83665, 88561, 91001, 106141, 117181, 124645, 126701, 134521, 136981, 141661, 162401, 171205, 176437

Offset: 1

Antti Karttunen, Dec 22 2020

nonn

From Antti Karttunen, Dec 26 2020: (Start)
Equally, squarefree composite numbers k of the form 4u+1 for which A336466(k) divides k-1. This follows because on squarefree n, A336466(n) = A053575(n).
No common terms with A016105, because 4xy + 2(x+y) + 1 does not divide 4xy + 3(x+y) + 2 for any distinct x, y >= 0 (where 4x+3 and 4y+3 are the two prime factors of Blum integers).
This can also seen by another way: If this sequence contained any Blum integers, then, because A016105 is a subsequence of A339817, we would have found a composite number n satisfying Lehmer's totient problem y * phi(n) = n-1, for some integer y > 1. But Lehmer proved that such solutions should have at least 7 distinct prime factors, while Blum integers have only two.
Moreover, it seems that none of the terms of A167181 may occur here, and a few of A137409 (i.e., of A125667). See A339875 for those terms.
(End)

			85 = 4*21 + 1 = 5*17, thus phi(85) = 4*16 = 64, the odd part of which is A000265(64) = 1, which certainly divides 85-1, therefore 85 is included as a term.
561 = 4*140 + 1 = 3*11*17, thus phi(561) = 2*10*16 = 320, the odd part of which is A000265(320) = 5, which divides 560, therefore 561 is included.

Antti Karttunen, Table of n, a(n) for n = 1..1316
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, A000265, A016105, A053575, A137409, A167181, A336466.
Subsequence of A005117.
Intersection of A091113 and A339880.
Cf. A339875 (a subsequence).
Cf. also comments in A339817.

odd[n_] := n/2^IntegerExponent[n, 2]; Select[4*Range[45000] + 1, CompositeQ[#] && Divisible[# - 1, odd[EulerPhi[#]]] &] (* Amiram Eldar, Feb 17 2021 *)

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

A339971 Odd part of A339821(n).

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 3, 3, 5, 5, 5, 5, 15, 15, 15, 15, 3, 3, 3, 3, 9, 9, 9, 9, 15, 15, 15, 15, 45, 45, 45, 45, 1, 1, 1, 1, 3, 3, 3, 3, 5, 5, 5, 5, 15, 15, 15, 15, 3, 3, 3, 3, 9, 9, 9, 9, 15, 15, 15, 15, 45, 45, 45, 45, 9, 9, 9, 9, 27, 27, 27, 27, 45, 45, 45, 45, 135, 135, 135, 135, 27, 27, 27, 27, 81, 81, 81, 81, 135

Offset: 0

Antti Karttunen, Dec 26 2020

nonn

Cf. A000010, A000265, A003961, A019565, A053575, A057023, A336466, A339821, A339822, A339970.

Cf. A339972 (quadrisection).

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

If 4n = 2^e1 + 2^e2 + ... + 2^ek [e1 ... ek distinct], then a(n) = A057023(e1) * A057023(e2) * ... * A057023(ek).
a(n) = A053575(A019565(2n)) = A336466(A003961(A019565(n))) = A000265(A339821(n)).
a(n) = A339821(n) / A000079(A339822(n)).

A336396 a(n) = A329697(n) - A087436(n).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 2, 0, 1, 1, 2, 0, 0, 1, 0, 1, 2, 0, 2, 0, 1, 0, 1, 0, 2, 2, 1, 0, 1, 1, 3, 1, 0, 2, 3, 0, 2, 0, 0, 1, 2, 0, 1, 1, 2, 2, 3, 0, 2, 2, 1, 0, 1, 1, 3, 0, 2, 1, 3, 0, 2, 2, 0, 2, 2, 1, 3, 0, 0, 1, 2, 1, 0, 3, 2, 1, 2, 0, 2, 2, 2, 3, 2, 0, 1, 2, 1, 0, 2, 0, 2, 1, 1

Offset: 1

Antti Karttunen, Jul 24 2020

nonn

Totally additive because both A087436 and A329697 are.

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

Cf. A000265, A046660, A087436, A329697, A336118, A336466, A336469.

A087436(n) = (bigomega(n>>valuation(n,2)));
A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
A336396(n) = (A329697(n) - A087436(n));

a(n) = A329697(n) - A087436(n).
a(n) = A329697(A336466(n)).
a(n) = A336469(n) - A046660(A000265(n)).
For all n >= 1, a(n) <= A336118(n).

A350067 Lexicographically earliest infinite sequence such that a(i) = a(j) => f(i) = f(j), where f(n) = [A342666(n), A350063(n)] for n > 1, with f(1) = 1.

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 2, 4, 3, 5, 2, 6, 2, 3, 3, 7, 2, 4, 2, 8, 5, 9, 2, 10, 3, 11, 4, 11, 2, 11, 2, 12, 3, 13, 3, 14, 2, 3, 9, 11, 2, 8, 2, 15, 6, 16, 2, 17, 3, 5, 11, 18, 2, 19, 5, 20, 13, 21, 2, 22, 2, 23, 8, 24, 3, 25, 2, 26, 3, 6, 2, 9, 2, 27, 4, 28, 3, 26, 2, 29, 7, 30, 2, 31, 9, 32, 16, 33, 2, 31, 5, 34, 21, 35

Offset: 1

Antti Karttunen, Jan 29 2022

nonn

Restricted growth sequence transform of the ordered pair [A342666(n), A350063(n)], when assuming that A342666(1) = 0.
Restricted growth sequence transform of the function f(1) = 0, f(n) = A336470(A156552(n)) for n > 1.
For all i, j >= 1: A305897(i) = A305897(j) => a(i) = a(j) => A350065(i) = A350065(j).
For all i, j >= 2: a(i) = a(j) => A342651(i) = A342651(j).

Antti Karttunen, Table of n, a(n) for n = 1..10000 (based on Hans Havermann's factorization of A156552)
Index entries for sequences computed from indices in prime factorization

Cf. A156552, A322993, A336466, A342666, A350063, A336470.

Cf. also A305897, A350065, A342651.

up_to = 3003;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A000265(n) = (n>>valuation(n,2));
A003958(n) = { my(f = factor(n)); for(i=1, #f~, f[i, 1]--); factorback(f); };
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ From A046523
A156552(n) = { my(f = factor(n), p, p2 = 1, res = 0); for(i = 1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p * p2 * (2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); res };
A336466(n) = { my(f=factor(n)); prod(k=1, #f~, A000265(f[k, 1]-1)^f[k, 2]); };
Aux350067(n) = if(1==n,1,my(u=A000265(A156552(n))); [A046523(u),A336466(u)]);
v350067 = rgs_transform(vector(up_to, n, Aux350067(n)));
A350067(n) = v350067[n];

A339903 Fully multiplicative with a(p) = A000265(q-1), where q = A151800(p), the next prime > p.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Dec 29 2020

Antti Karttunen, Table of n, a(n) for n = 1..8191
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Index entries for sequences computed from indices in prime factorization

Cf. A000265, A003958, A003961, A005117, A151800, A339904.

A000265(n) = (n>>valuation(n,2));
A339903(n) = if(1==n,n,my(f=factor(n)); for(i=1,#f~,f[i,1] = nextprime(1+f[i,1])-1); A000265(factorback(f)));

a(n) = A336466(A003961(n)) = A000265(A003958(A003961(n))).

For all squarefree numbers k, a(k) = A339904(k).

A366789 Fully multiplicative with a(p) = oddpart(primepi(p)).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 5, 1, 3, 1, 3, 1, 7, 1, 1, 3, 1, 5, 9, 1, 9, 3, 1, 1, 5, 3, 11, 1, 5, 7, 3, 1, 3, 1, 3, 3, 13, 1, 7, 5, 3, 9, 15, 1, 1, 9, 7, 3, 1, 1, 15, 1, 1, 5, 17, 3, 9, 11, 1, 1, 9, 5, 19, 7, 9, 3, 5, 1, 21, 3, 9, 1, 5, 3, 11, 3, 1, 13, 23, 1, 21, 7, 5, 5, 3, 3, 3, 9, 11, 15, 3, 1, 25, 1, 5, 9

Offset: 1

Antti Karttunen, Oct 23 2023

Cf. A000265, A000720, A003963, A366790.

Cf. also A336466.

{1}~Join~Array[#/2^IntegerExponent[#, 2] &@ Apply[Times, PrimePi[#1]^#2 & @@@ FactorInteger[#]] &, 120, 2] (* Michael De Vlieger, Oct 23 2023 *)

A000265(n) = (n>>valuation(n,2));
A366789(n) = { my(f=factor(n)); prod(k=1, #f~, A000265(primepi(f[k, 1]))^f[k, 2]); };

a(n) = A000265(A003963(n)).

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.

Original entry on oeis.org

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.

A365394 Lexicographically earliest infinite sequence such that a(i) = a(j) => A365425(i) = A365425(j) and A365426(i) = A365426(j) for all i, j >= 0.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 2, 2, 1, 4, 3, 3, 2, 5, 2, 6, 1, 7, 4, 4, 3, 8, 3, 9, 2, 8, 5, 10, 2, 10, 6, 11, 1, 12, 7, 7, 4, 13, 4, 14, 3, 15, 8, 16, 3, 16, 9, 17, 2, 13, 8, 18, 5, 19, 10, 20, 2, 18, 10, 21, 6, 21, 11, 6, 1, 22, 12, 12, 7, 23, 7, 24, 4, 25, 13, 26, 4, 26, 14, 27, 3, 25, 15, 28, 8, 29, 16, 30, 3, 28, 16, 31, 9, 31, 17

Offset: 0

Antti Karttunen, Sep 04 2023

Restricted growth sequence transform of the ordered pair [A365425(n), A365426(n)].
Restricted growth sequence transform of the function f(n) = A336470(A163511(n)).
For all i, j: a(i) = a(j) => A334204(i) = A334204(j).

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

Cf. A000265, A003602, A046523, A163511, A336470, A365425, A365426.

Cf. also A350067, A365395, A366792 (compare the scatter plots).

up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A000265(n) = (n>>valuation(n,2));
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); }; \\ From A046523
A163511(n) = if(!n, 1, my(p=2, t=1); while(n>1, if(!(n%2), (t*=p), p=nextprime(1+p)); n >>= 1); (t*p));
A365425(n) = A046523(A000265(A163511(n)));
A336466(n) = { my(f=factor(n)); prod(k=1, #f~, A000265(f[k, 1]-1)^f[k, 2]); };
A365426(n) = A336466(A163511(n));
A365394aux(n) = [A365425(n), A365426(n)];
v365394 = rgs_transform(vector(1+up_to,n,A365394aux(n-1)));
A365394(n) = v365394[1+n];

For all n >= 1, a(n) = a(2*n) = a(A000265(n)).

A359587 Fully multiplicative with a(p) = A008578(1+A329697(p)).

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 1, 4, 2, 3, 2, 3, 3, 4, 1, 2, 4, 5, 2, 6, 3, 5, 2, 4, 3, 8, 3, 5, 4, 5, 1, 6, 2, 6, 4, 5, 5, 6, 2, 3, 6, 7, 3, 8, 5, 7, 2, 9, 4, 4, 3, 5, 8, 6, 3, 10, 5, 7, 4, 5, 5, 12, 1, 6, 6, 7, 2, 10, 6, 7, 4, 5, 5, 8, 5, 9, 6, 7, 2, 16, 3, 5, 6, 4, 7, 10, 3, 5, 8, 9, 5, 10, 7, 10, 2, 3, 9, 12, 4, 5, 4, 5, 3, 12

Offset: 1

Antti Karttunen, Jan 08 2023

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A000265, A001222, A008578, A056239, A087436, A318995, A329697, A336396, A336466.

A008578(n) = if(1==n,1,prime(n-1));
A329697(n) = if(!bitand(n, n-1), 0, 1+A329697(n-(n/vecmax(factor(n)[, 1]))));
A359587(n) = { my(f=factor(n)); for(i=1, #f~, f[i, 1] = A008578(1+A329697(f[i, 1]))); factorback(f); };

For n >= 1: (Start)
a(A000265(n)) = a(2*n) = a(n).
A001222(a(n)) = A087436(n),
A056239(a(n)) = A329697(n),
A318995(a(n)) = A336396(n) = A329697(A336466(n)).
(End)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A339971 Odd part of A339821(n).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A336396 a(n) = A329697(n) - A087436(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A350067 Lexicographically earliest infinite sequence such that a(i) = a(j) => f(i) = f(j), where f(n) = [A342666(n), A350063(n)] for n > 1, with f(1) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A339903 Fully multiplicative with a(p) = A000265(q-1), where q = A151800(p), the next prime > p.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A366789 Fully multiplicative with a(p) = oddpart(primepi(p)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

A365394 Lexicographically earliest infinite sequence such that a(i) = a(j) => A365425(i) = A365425(j) and A365426(i) = A365426(j) for all i, j >= 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A359587 Fully multiplicative with a(p) = A008578(1+A329697(p)).

Views

Author

Keywords

Links