A247074 -id:A247074 - cp's OEIS frontend

A340149 Odd part of A340147: a(n) = A000265(A247074(A003961(n))).

1, 1, 1, 3, 1, 1, 1, 9, 5, 3, 1, 3, 1, 5, 3, 27, 1, 5, 1, 9, 5, 3, 1, 9, 7, 1, 25, 15, 1, 3, 1, 81, 3, 9, 15, 15, 1, 11, 1, 27, 1, 5, 1, 9, 5, 7, 1, 27, 11, 21, 9, 3, 1, 25, 1, 45, 11, 15, 1, 9, 1, 9, 25, 243, 3, 3, 1, 27, 7, 3, 1, 45, 1, 5, 21, 33, 15, 1, 1, 81, 125, 21, 1, 15, 3, 23, 15, 27, 1, 15, 5, 21, 9, 13, 33

Offset: 1

Antti Karttunen, Dec 30 2020

nonn

Each term a(n) is a divisor of A340075(n), at n=85 occurs the first proper divisor.

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

Cf. A000265, A003961, A247074, A340147, A340150 (positions of ones).

Differs from related A340075 for the first time at n=85, where a(85) = 3, while A340075(85) = 9.

A000265(n) = (n>>valuation(n,2));
A003961(n) = { my(f = factor(n)); for(i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); };
A247074(n) = { my(f=factor(n)); eulerphi(f)/prod(i=1, #f~, gcd(f[i, 1]-1, n-1)); }; \\ From A247074
A340149(n) = A000265(A247074(A003961(n)));

a(n) = A000265(A340147(n)) = A000265(A247074(A003961(n))).

A340145 Dirichlet inverse of A247074(x) = phi(x)/(Product_{primes p dividing x} gcd(p-1, x-1)).

Original entry on oeis.org

1, -1, -1, -1, -1, 0, -1, -1, -2, -2, -1, 1, -1, -4, 0, -1, -1, 1, -1, 1, -1, -8, -1, 2, -4, -10, -4, 9, -1, 2, -1, -1, -3, -14, -4, 3, -1, -16, -4, 4, -1, 4, -1, 1, 4, -20, -1, 3, -6, -5, -6, 17, -1, 4, -8, -10, -7, -26, -1, 6, -1, -28, 0, -1, -1, 24, -1, 1, -9, 18, -1, 4, -1, -34, 1, 25, -13, 10, -1, 7, -8, -38, -1

Offset: 1

Antti Karttunen, Dec 29 2020

sign

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

Cf. A247074.

Cf. also A340142, A340144, A340146.

up_to = 65537;
A247074(n) = { my(f=factor(n)); eulerphi(f)/prod(i=1, #f~, gcd(f[i, 1]-1, n-1)); }; \\ From A247074
DirInverse(v) = { my(u=vector(#v)); u[1] = (1/v[1]); for(n=2, #v, u[n] = -sumdiv(n, d, if(dA247074(n)));
A340145(n) = v340145[n];

A340146 Möbius transform of A247074(x) = phi(x)/(Product_{primes p dividing x} gcd(p-1, x-1)).

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 0, 2, 2, 3, 0, 1, 0, 5, 1, 4, 0, 2, 0, 3, 2, 9, 0, 2, 4, 11, 6, -3, 0, 2, 0, 8, 4, 15, 5, 4, 0, 17, 5, 6, 0, 3, 0, 9, -1, 21, 0, 4, 6, 12, 7, -5, 0, 6, 9, 18, 8, 27, 0, 3, 0, 29, 4, 16, 2, -11, 0, 15, 10, -6, 0, 8, 0, 35, 4, -7, 14, 6, 0, 12, 18, 39, 0, 13, 3, 41, 13, 18, 0, 13, 1, 21, 14, 45, 17, 8

Offset: 1

Antti Karttunen, Dec 29 2020

sign

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

Cf. A008683, A247074.

Cf. also A340143, A340144, A340145.

A247074(n) = { my(f=factor(n)); eulerphi(f)/prod(i=1, #f~, gcd(f[i, 1]-1, n-1)); }; \\ From A247074
A340146(n) = sumdiv(n,d,moebius(n/d)*A247074(d));

a(n) = Sum_{d|n} A008683(n/d) * A247074(d).

A340144 Numerators of the sequence whose Dirichlet convolution with itself yields sequence A247074(x) = phi(x)/(Product_{primes p dividing x} gcd(p-1, x-1)).

Original entry on oeis.org

1, 1, 1, 7, 1, 3, 1, 25, 11, 7, 1, 19, 1, 11, 3, 363, 1, 31, 1, 43, 5, 19, 1, 63, 19, 23, 61, 3, 1, 19, 1, 1335, 9, 31, 11, 189, 1, 35, 11, 139, 1, 29, 1, 115, 7, 43, 1, 867, 27, 127, 15, 11, 1, 163, 19, 279, 17, 55, 1, 93, 1, 59, 51, 9923, 5, -15, 1, 187, 21, 3, 1, 615, 1, 71, 55, 19, 29, 59, 1, 1875, 1363, 79, 1, 203

Offset: 1

Antti Karttunen, Dec 29 2020

			For n = 561 = 3*11*17, its divisors d are: 1, 3, 11, 17, 33, 51, 187, 561.
For this sequence, the corresponding terms a(d) are: 1, 1, 1, 1, 9, 15, 79, -99.
For A046644, the corresponding terms are:            1, 2, 2, 2, 4,  4,  4,   8.
Convolving these ratios as Sum_{d|561} r(d)*r(n/d) = 2*((1/1)*(-99/8) + (1/2)*(79/4) + (1/2)*(15/4) + (1/2)*(9/4)) yields 1 as expected, because 561 is Carmichael number (A002997) and A247074 obtains value 1 on all of them.

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

Cf. A046644 (denominators).
Cf. A247074.
Cf. also A340141, A340145, A340146.

up_to = 65537;
A247074(n) = { my(f=factor(n)); eulerphi(f)/prod(i=1, #f~, gcd(f[i, 1]-1, n-1)); }; \\ From A247074
DirSqrt(v) = {my(n=#v, u=vector(n)); u[1]=1; for(n=2, n, u[n]=(v[n]/v[1] - sumdiv(n, d, if(d>1&&dA247074(n)));
A340144(n) = numerator(v340144rat[n]);

A340147 a(n) = A247074(A003961(n)).

Original entry on oeis.org

1, 1, 1, 3, 1, 2, 1, 9, 5, 3, 1, 3, 1, 5, 6, 27, 1, 10, 1, 9, 10, 6, 1, 18, 7, 8, 25, 15, 1, 3, 1, 81, 3, 9, 15, 15, 1, 11, 4, 27, 1, 5, 1, 9, 10, 14, 1, 27, 11, 21, 18, 6, 1, 50, 2, 45, 22, 15, 1, 18, 1, 18, 50, 243, 24, 12, 1, 27, 7, 3, 1, 90, 1, 20, 21, 33, 30, 16, 1, 81, 125, 21, 1, 30, 3, 23, 30, 54, 1, 15, 40, 21

Offset: 1

Antti Karttunen, Dec 30 2020

nonn

Prime shifted analog of A247074.

Each term a(n) is a divisor of A340072(n).

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. A003961, A003972, A247074, A340072, A340148, A340149 (odd part).

A003961(n) = { my(f = factor(n)); for(i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); };
A247074(n) = { my(f=factor(n)); eulerphi(f)/prod(i=1, #f~, gcd(f[i, 1]-1, n-1)); }; \\ From A247074
A340147(n) = A247074(A003961(n));

a(n) = A247074(A003961(n)).

a(n) = A003972(n) / A340148(n).

A160595 Numerator of resilience R(n) = phi(n)/(n-1), with a(1) = 1 by convention.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 3, 4, 1, 4, 1, 6, 4, 8, 1, 6, 1, 8, 3, 10, 1, 8, 5, 12, 9, 4, 1, 8, 1, 16, 5, 16, 12, 12, 1, 18, 12, 16, 1, 12, 1, 20, 6, 22, 1, 16, 7, 20, 16, 8, 1, 18, 20, 24, 9, 28, 1, 16, 1, 30, 18, 32, 3, 4, 1, 32, 11, 8, 1, 24, 1, 36, 20, 12, 15, 24, 1, 32, 27, 40, 1, 24, 16, 42, 28

Offset: 1

M. F. Hasler, May 23 2009

The resilience of a denominator, R(d), is the ratio of proper fractions n/d, 0 < n < d, that are resilient, i.e., such that gcd(n, d) = 1. Obviously this is the case for phi(d) proper fractions among the d - 1 possible ones.
a(n) = 1 if n is prime. It is unknown whether there exist composite n with a(n) = 1 (see Wikipedia link). - Robert Israel, Dec 26 2016
Conjecture: a(n) > 2 for every composite n > 6. Slightly stronger than the Lehmer's totient conjecture (1932). - Thomas Ordowski, Mar 13 2019

			a(9) = 3 since for the denominator d = 9, among the 8 proper fractions n/9 (n = 1, ..., 8), six cannot be canceled down by a common factor (namely 1/9, 2/9, 4/9, 5/9, 7/9, 8/9), thus R(9) = 6/8 = 3/4.

Antti Karttunen, Table of n, a(n) for n = 1..65537 (terms 2..10000 from Robert Israel)
Project Euler, Problem 245: resilient fractions, May 2009
Wikipedia, Lehmer's totient problem.

Cf. A000010, A049559, A247074, A318829.

[Numerator(EulerPhi(n)/(n-1)): n in [2..90]]; // Vincenzo Librandi, Jan 02 2017

seq(numer(numtheory:-phi(n)/(n-1)),n=2..100); # Robert Israel, Dec 26 2016

Numerator[Table[EulerPhi[n]/(n - 1), {n, 2, 87}]] (* Alonso del Arte, Sep 19 2011 *)

A160595(n) = if(1==n,n,numerator(eulerphi(n)/(n-1)));

a(n) = phi(n)/gcd(phi(n),n-1) = A000010(n) / A049559(n) = A247074(n) * A318829(n). - Antti Karttunen, Sep 09 2018

Term a(1) = 1 prepended by Antti Karttunen, Sep 09 2018

A323405 Lexicographically earliest sequence such that for all i, j, a(i) = a(j) => f(i) = f(j) where f(n) = [A003557(n), A023900(n), A063994(n)] for all other numbers, except f(n) = 0 for odd primes.

Original entry on oeis.org

1, 2, 3, 4, 3, 5, 3, 6, 7, 8, 3, 9, 3, 10, 11, 12, 3, 13, 3, 14, 15, 16, 3, 17, 18, 19, 20, 21, 3, 22, 3, 23, 24, 25, 26, 27, 3, 28, 26, 29, 3, 30, 3, 31, 32, 33, 3, 34, 35, 36, 37, 38, 3, 39, 40, 41, 42, 43, 3, 44, 3, 45, 46, 47, 48, 49, 3, 50, 51, 52, 3, 53, 3, 54, 55, 56, 57, 58, 3, 59, 60, 61, 3, 62, 63, 64, 65, 66, 3, 67, 68, 69, 57, 70, 71, 72, 3, 73, 74, 75, 3

Offset: 1

Antti Karttunen, Jan 13 2019

nonn

For all i, j:
  A305801(i) = A305801(j) => a(i) = a(j),
  a(i) = a(j) => A323371(i) = A323371(j),
  a(i) = a(j) => A247074(i) = A247074(j).

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

Cf. A000010, A003557, A023900, A063994, A247074, A305801, A323371, A323404.
Differs from A323370 for the first time at n=78, where a(78) = 58, while A323370(78) = 52.
Cf. also A323374.

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; };
A003557(n) = { my(f=factor(n)); for (i=1, #f~, f[i, 2] = max(0,f[i, 2]-1)); factorback(f); };
A023900(n) = sumdivmult(n, d, d*moebius(d)); \\ From A023900
A063994(n) = { my(f=factor(n)[, 1]); prod(i=1, #f, gcd(f[i]-1, n-1)); }; \\ From A063994
Aux323405(n) = if((n>2)&&isprime(n),0,[A003557(n), A023900(n), A063994(n)]);
v323405 = rgs_transform(vector(up_to, n, Aux323405(n)));
A323405(n) = v323405[n];

A318829 a(n) = A063994(n) / A049559(n) = (1/gcd(n-1, phi(n))) * Product_{primes p dividing n} gcd(p-1, n-1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2

Offset: 1

Antti Karttunen, Sep 09 2018

nonn

Records occur at: 1, 15, 85, 247, 671, 949, 1105, 1387, 2047, 2821, 9471, 11305, 13747, 13981, 29341, 40885, 51319, 63973, ...

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

Cf. A049559, A063994, A160595, A247074, A318828.

A049559(n) = gcd(eulerphi(n), n-1); \\ From A049559
A063994(n) = { my(f=factor(n)[,1]); prod(i=1, #f, gcd(f[i]-1, n-1)); };
A318829(n) = (A063994(n)/A049559(n));

a(n) = A063994(n) / A049559(n).

a(n) = A160595(n) / A247074(n).

A323404 Lexicographically earliest sequence such that for all i, j, a(i) = a(j) => f(i) = f(j) where f(n) = [A003557(n), A023900(n), A063994(n)].

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 35, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 76, 92

Offset: 1

Antti Karttunen, Jan 13 2019

nonn

For all i, j: a(i) = a(j) => A247074(i) = A247074(j).

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

Cf. A000010, A003557, A023900, A063994, A247074, A323405.

Cf. also A323373.

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; };
A003557(n) = { my(f=factor(n)); for (i=1, #f~, f[i, 2] = max(0,f[i, 2]-1)); factorback(f); };
A023900(n) = sumdivmult(n, d, d*moebius(d)); \\ From A023900
A063994(n) = { my(f=factor(n)[, 1]); prod(i=1, #f, gcd(f[i]-1, n-1)); }; \\ From A063994
Aux323404(n) = if(1,[A003557(n), A023900(n), A063994(n)]);
v323404 = rgs_transform(vector(up_to, n, Aux323404(n)));
A323404(n) = v323404[n];

A340091 Odd numbers k such that A064989(k) is in A340151.

Original entry on oeis.org

679, 703, 1387, 1729, 1891, 2047, 2509, 2701, 2821, 3277, 3367, 5551, 7471, 7735, 8119, 8827, 9997, 10963, 11305, 12403, 13021, 13747, 13981, 14491, 14701, 15841, 16471, 17563, 19951, 21349, 21907, 21931, 22015, 23959, 24727, 25669, 26281, 27511, 28939, 29341, 31417, 32407, 38503, 39091, 39831, 39865, 40501, 41041

Offset: 1

Antti Karttunen, Dec 31 2020

nonn

Sequence A003961(A340151(i)), for i >= 1, sorted into ascending order.

By definition, this has no common terms with A340077 nor any of its subsequences like A339869 or A339880.

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

Cf. A002997, A003961, A339869, A339880, A340077, A340151.

Cf. A340092 (Carmichael numbers in this sequence).

A000265(n) = (n>>valuation(n,2));
A003961(n) = { my(f = factor(n)); for(i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); };
A339904(n) = A000265(eulerphi(A003961(n)));
A340075(n) = { my(u=A339904(n)); u/gcd(A003961(n)-1, u); };
A247074(n) = { my(f=factor(n)); eulerphi(f)/prod(i=1, #f~, gcd(f[i, 1]-1, n-1)); }; \\ From A247074
A340149(n) = A000265(A247074(A003961(n)));
isA340151(n) = ((1!=A340075(n))&&(1==A340149(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) };
isA340091(n) = ((n%2)&&isA340151(A064989(n)));

cp's OEIS Frontend

A340149 Odd part of A340147: a(n) = A000265(A247074(A003961(n))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A340145 Dirichlet inverse of A247074(x) = phi(x)/(Product_{primes p dividing x} gcd(p-1, x-1)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A340146 Möbius transform of A247074(x) = phi(x)/(Product_{primes p dividing x} gcd(p-1, x-1)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A340144 Numerators of the sequence whose Dirichlet convolution with itself yields sequence A247074(x) = phi(x)/(Product_{primes p dividing x} gcd(p-1, x-1)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A340147 a(n) = A247074(A003961(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A160595 Numerator of resilience R(n) = phi(n)/(n-1), with a(1) = 1 by convention.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A323405 Lexicographically earliest sequence such that for all i, j, a(i) = a(j) => f(i) = f(j) where f(n) = [A003557(n), A023900(n), A063994(n)] for all other numbers, except f(n) = 0 for odd primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A318829 a(n) = A063994(n) / A049559(n) = (1/gcd(n-1, phi(n))) * Product_{primes p dividing n} gcd(p-1, n-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI