A000010 -id:A000010 - cp's OEIS frontend

A079124 Number of ways to partition n into distinct positive integers <= phi(n), where phi is Euler's totient function (A000010).

1, 1, 0, 1, 0, 2, 0, 4, 1, 5, 1, 11, 0, 17, 4, 13, 13, 37, 2, 53, 13, 51, 35, 103, 10, 135, 78, 167, 89, 255, 4, 339, 253, 378, 306, 542, 121, 759, 558, 872, 498, 1259, 121, 1609, 1180, 1677, 1665, 2589, 808, 3250, 1969, 3844, 3325, 5119, 1850, 6268, 4758, 7546, 7070

Offset: 0

Reinhard Zumkeller, Dec 27 2002

nonn

Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education, Vol. 31, No. 1, pp. 24-28, Winter 1997. MathEduc Database (Zentralblatt MATH, 1997c.01891).

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17. Zentralblatt MATH, Zbl 1071.05501.

Cf. A079126, A000009, A079122, A079125, A067953.

Cf. A227296, A036998.

a079124 n = p [1 .. a000010 n] n where
   p _      0 = 1
   p []     _ = 0
   p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
-- Reinhard Zumkeller, Jul 05 2013

with(numtheory):
b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, b(n, i-1)+`if`(i>n, 0, b(n-i, i-1))))
    end:
a:= n-> b(n, phi(n)):
seq(a(n), n=0..100);  # Alois P. Heinz, May 11 2015

b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, b[n, i-1] + If[i>n, 0, b[n-i, i-1]]]]; a[n_] := b[n, EulerPhi[n]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jun 30 2015, after Alois P. Heinz *)

a(n) = b(0, n), b(m, n) = 1 + sum(b(i, j): m

a(0)=1 prepended by Alois P. Heinz, May 11 2015

A082061 Greatest common prime divisor of n and phi(n)=A000010(n); a(n)=1 if no common prime divisor exists.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 3, 2, 1, 2, 5, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 3, 2, 1, 3, 1, 2, 3, 2, 1, 2, 7, 5, 1, 2, 1, 3, 5, 2, 3, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 5, 2, 1, 3, 1, 2, 3, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 3, 2, 1, 2, 1, 7, 3, 5, 1, 2, 1, 2, 3

Offset: 1

Labos Elemer, Apr 07 2003

nonn

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

Cf. A000010, A003277, A006530, A009195, A070003.

Cf. also A082062, A082063, A082064, A082065, A082066, A082067.

gcpd := proc(a,b) local g ,d ; g := 1 ; for d in numtheory[divisors](a) intersect numtheory[divisors](b) do if isprime(d) then g := max(g,d) ; end if; end do: g ; end proc:
A082061 := proc(n) gcpd( numtheory[phi](n), n) ; end proc: # R. J. Mathar, Jul 09 2011

(* factors/exponent SET *) ffi[x_] := Flatten[FactorInteger[x]]; lf[x_] := Length[FactorInteger[x]]; ba[x_] := Table[Part[ffi[x], 2*w-1], {w, 1, lf[x]}]; f1[x_] := x; f2[x_] := EulerPhi[x]; Table[Max[Intersection[ba[f1[w]], ba[f2[w]]]], {w, 1, 128}]
(* Second program: *)
Array[If[CoprimeQ[#1, #2], 1, Max@ Apply[Intersection, Map[FactorInteger[#][[All, 1]] &, {#1, #2}]]] & @@ {#, EulerPhi@ #} &, 105] (* Michael De Vlieger, Nov 03 2017 *)

gpf(n)=if(n>1,my(f=factor(n)[,1]);f[#f],1)
a(n)=gpf(gcd(eulerphi(n),n)) \\ Charles R Greathouse IV, Feb 19 2013

a(n) = A006530(A009195(n)). - Antti Karttunen, Nov 03 2017
From Amiram Eldar, Dec 06 2024: (Start)
a(n) <= A006530(n), with equality if and only if n is in A070003.
a(n) = 1 if and only if n is a cyclic number (A003277). (End)

Changed "was found" to "exists" in definition. - N. J. A. Sloane, Jan 29 2022

A082065 Greatest common prime-divisor of phi(n)=A000010(n) and sigma(2,n) = A001157(n); a(n) = 1 if no common prime-divisor exists.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 1, 2, 2, 2, 5, 2, 2, 1, 2, 2, 3, 2, 2, 2, 1, 5, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 5, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 2, 1, 2, 5, 2, 2, 2, 2, 2, 1, 2, 2, 5, 3, 5, 2, 2, 2, 1, 5, 2, 3, 2, 2, 2, 5, 2, 2, 2, 2, 5, 2, 2, 2, 2, 3, 2, 1

Offset: 1

Labos Elemer, Apr 07 2003

nonn

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A006530, A001157, A000010, A082061-A082066.

gcpd := proc(a,b) local g ,d ; g := 1 ; for d in numtheory[divisors](a) intersect numtheory[divisors](b) do if isprime(d) then g := max(g,d) ; end if; end do: g ; end proc:
A082065 := proc(n) gcpd( numtheory[phi](n), numtheory[sigma][2](n) ) ; end proc:
seq(A082065(n),n=1..120) ; # R. J. Mathar, Jul 09 2011

Table[FactorInteger[GCD[EulerPhi@ n, DivisorSigma[2, n]]][[-1, 1]], {n, 100}] (* Michael De Vlieger, Jul 22 2017 *)

gpf(n)=if(n>1,my(f=factor(n)[,1]);f[#f],1)
a(n)=gpf(gcd(eulerphi(n),sigma(n,2))) \\ Charles R Greathouse IV, Feb 21 2013

Values corrected by R. J. Mathar, Jul 09 2011

Changed "was found" to "exists" in definition. - N. J. A. Sloane, Jan 29 2022

A082067 Smallest prime that divides n and phi(n)=A000010(n), or 1 if n and phi(n) are relatively prime.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 5, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 3, 2, 1, 2, 7, 2, 1, 2, 1, 2, 5, 2, 3, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 5, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 3, 2, 1, 2, 1, 2, 3

Offset: 1

Labos Elemer, Apr 07 2003

nonn

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

Cf. A000010, A009195.

Cf. also A082061, A082068, A082069, A082070, A082071, A082072.

ffi[x_] := Flatten[FactorInteger[x]]; lf[x_] := Length[FactorInteger[x]]; ba[x_] := Table[Part[ffi[x], 2*w-1], {w, 1, lf[x]}]; f1[x_] := n; f2[x_] := EulerPhi[x]; Table[Min[Intersection[ba[f1[w]], ba[f2[w]]]], {w, 1, 128}]
(* Second program: *)
Array[If[CoprimeQ[#1, #2], 1, Min@ Apply[Intersection, Map[FactorInteger[#][[All, 1]] &, {#1, #2}]]] & @@ {#, EulerPhi@ #} &, 105] (* Michael De Vlieger, Nov 03 2017 *)

A020639(n) = if(1==n,n,vecmin(factor(n)[, 1]));
A082067(n) = A020639(gcd(eulerphi(n), n)); \\ Antti Karttunen, Nov 03 2017

a(n) = A020639(A009195(n)). - Antti Karttunen, Nov 03 2017

Name clarified by Antti Karttunen, Nov 03 2017

A098189 Sum of unitary divisors minus Euler phi: a(n) = A034448(n) - A000010(n).

Original entry on oeis.org

0, 2, 2, 3, 2, 10, 2, 5, 4, 14, 2, 16, 2, 18, 16, 9, 2, 24, 2, 22, 20, 26, 2, 28, 6, 30, 10, 28, 2, 64, 2, 17, 28, 38, 24, 38, 2, 42, 32, 38, 2, 84, 2, 40, 36, 50, 2, 52, 8, 58, 40, 46, 2, 66, 32, 48, 44, 62, 2, 104, 2, 66, 44, 33, 36, 124, 2, 58, 52, 120, 2, 66, 2, 78, 64, 64, 36, 144, 2

Offset: 1

Labos Elemer, Sep 03 2004

nonn

			a(1) = 1 - 1 = 0.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A034448, A000010, A063919, A098190, A098191, A098192, A098193, A098194, A098195.

Table[DivisorSum[n, # &, CoprimeQ[#, n/#] &] - EulerPhi@ n, {n, 120}] (* Michael De Vlieger, Mar 01 2017 *)

a(n) = sumdiv(n, d, if(gcd(d, n/d)==1, d)) - eulerphi(n); \\ Michel Marcus, Feb 25 2014

a(n)=my(f=factor(n)); prod(k=1, #f[, 2], f[k, 1]^f[k, 2]+1) - eulerphi(f) \\ Charles R Greathouse IV, Mar 01 2017

a(n) > A063919(n) if n > 1.
a(A000040(k)) = 2.
Sum_{k=1..n} a(k) ~ c * n^2, where c = Pi^2/(12*zeta(3)) - 3/Pi^2 = 0.380252... . - Amiram Eldar, Aug 21 2023

Edited by R. J. Mathar, Mar 02 2009

A110086 Numbers k such that sigma(k) - phi(k) <= tau(k)^omega(k), where sigma = A000203, phi = A000010, tau = A000005 and omega = A001221.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 10, 11, 12, 13, 15, 17, 18, 19, 20, 23, 24, 29, 30, 31, 36, 37, 41, 42, 43, 47, 53, 59, 60, 61, 66, 67, 70, 71, 73, 78, 79, 83, 84, 89, 90, 97, 101, 102, 103, 105, 107, 109, 110, 113, 114, 120, 126, 127, 130, 131, 132, 137, 138, 139, 140, 149, 150, 151

Offset: 1

Reinhard Zumkeller, Jul 11 2005

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Union of A000040 and A110085.
Complement of A110086.
Cf. A000005, A000010, A000203, A001221, A051612, A110088, A240960 (subsequence).

a110086 n = a110086_list !! (n-1)
a110086_list = filter (\x -> a051612 x <= a110088 x) [1..]
-- Reinhard Zumkeller, Aug 05 2014

q[k_] := DivisorSigma[1, k] - EulerPhi[k] <= DivisorSigma[0, k]^PrimeNu[k]; Select[Range[160], q] (* Amiram Eldar, Sep 15 2024 *)

is(n)=sigma(n)-eulerphi(n)<=numdiv(n)^omega(n) \\ Charles R Greathouse IV, Feb 14 2013

A051612(a(n)) <= A110088(a(n)).

A147619 Numbers n = concat(a,b) such that phi(n) = phi(a) * phi(b), where phi = A000010.

Original entry on oeis.org

78, 780, 897, 918, 1179, 1365, 1776, 2574, 2598, 2967, 3168, 3762, 4758, 5775, 5796, 7800, 7875, 7917, 8217, 8970, 9180, 9576, 11790, 13650, 13662, 13875, 13896, 14391, 17760, 18564, 18858, 19812, 20097, 25740, 25935, 25974, 25980, 27573, 28776

Offset: 1

M. F. Hasler, Nov 08 2008

Concat(a,b) means decimal concatenation of a and b, i.e., a*10^floor(log_10(b)+1) + b, since we do not allow leading zeros in b. However, allowing for leading zeros in b would not give any additional term below 10^6.
This sequence was suggested by Farideh Firoozbakht and David Wilson on the SeqFan mailing list, Oct 27 and Nov 06 2008 (see Links).
Farideh Firoozbakht has proved that if n is in this sequence, then n*10 is again in the sequence. Thus one could call "primitive" terms of this sequence those which aren't multiples of 10.
A possible variant would be to allow decomposition of n into an arbitrary number of substrings. If one requires decomposition of n into each of its digits, i.e., the analog of A098771 with sigma replaced by phi, then 78 appears to be the only number having this property.

Paolo P. Lava, Table of n, a(n) for n = 1..500
David Wilson, A nice (decimal) property of 78, Seqfan mailing list (Nov 2008).

Cf. A000010, A147616 (analog for sigma), A147624 (analog for omega), A147627 (analog for bigomega).

with(numtheory): P:=proc(q) local s, t, k, n; for n from 1 to q do
for k from 1 to ilog10(n) do s:=n mod 10^k; t:=trunc(n/10^k);
if s*t>0 then if phi(s)*phi(t)=phi(n)
then print(n); break; fi; fi; od; od; end: P(10^5); # Paolo P. Lava, Jan 27 2015

is_A147619(n)={ local(p=1, s=eulerphi(n)); while( n>p*=10, n%p*10

A156834 A156348 * A000010.

Original entry on oeis.org

1, 2, 3, 5, 5, 12, 7, 17, 19, 30, 11, 63, 13, 56, 99, 89, 17, 154, 19, 269, 237, 132, 23, 509, 301, 182, 379, 783, 29, 1230, 31, 881, 813, 306, 2125, 2431, 37, 380, 1299, 4157, 41, 4822, 43, 3695, 6175, 552, 47, 8529, 5587, 6266, 2787

Offset: 1

Gary W. Adamson, Feb 16 2009

Conjecture: for n>1, a(n) = n iff n is prime. Companion to A156833.

			a(4) = 5 = (1, 2, 0, 1) dot (1, 1, 2, 2) = (1 + 2 + 0 + 2), where row 4 of A156348 = (1, 2, 0, 1) and (1, 1, 2, 2) = the first 4 terms of Euler's phi function.

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Cf. A156348, A000010, A156833, A157020, A343553.

Equals row sums of triangle A157030. [Gary W. Adamson, Feb 21 2009]

A156834 := proc(n)
        add(A156348(n,k)*numtheory[phi](k),k=1..n) ;
end proc: # R. J. Mathar, Mar 03 2013

a[n_] := DivisorSum[n, EulerPhi[#] * Binomial[# + n/# - 2, #-1] &]; Array[a, 100] (* Amiram Eldar, Apr 22 2021 *)

a(n) = sumdiv(n, d, eulerphi(d)*binomial(d+n/d-2, d-1)); \\ Seiichi Manyama, Apr 22 2021

my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, eulerphi(k)*(x/(1-x^k))^k)) \\ Seiichi Manyama, Apr 22 2021

Equals A156348 * A054525 * [1, 2, 3,...]; where A054525 = the inverse Mobius transform.
a(n) = Sum_{d|n} phi(d) * binomial(d+n/d-2, d-1). - Seiichi Manyama, Apr 22 2021
G.f.: Sum_{k >= 1} phi(k) * (x/(1 - x^k))^k. - Seiichi Manyama, Apr 22 2021

Extended beyond a(14) by R. J. Mathar, Mar 03 2013

A179189 Numbers n such that phi(n) = phi(n+7), with Euler's totient function phi = A000010.

Original entry on oeis.org

5, 7, 21, 45, 75, 105, 285, 488, 585, 765, 1148, 1275, 1358, 1785, 2528, 3465, 4088, 6825, 9405, 12375, 14348, 15345, 16208, 16988, 23648, 25905, 25935, 42698, 50018, 52845, 54615, 61448, 62865, 68445, 78195, 80025, 82005, 88328, 93555, 98475

Offset: 1

M. F. Hasler, Jan 05 2011

nonn

There are 40 terms below 10^5, 81 terms below 10^6 and 162 terms below 10^7.  There are 6606 terms below 10^12. [Jud McCranie, Feb 13 2012]
Farideh Firoozbakht asks whether there is some a(n+1) = a(n)+7, cf. link.
For n < 10^13, the only n such that phi(n-7) = phi(n) = phi(n+7) is 30057431145. - Giovanni Resta, Feb 27 2014

Jud McCranie, Table of n, a(n) for n = 1..6606 (terms < 10^12)
F. Firoozbakht, Puzzle 466. phi(n-1)=phi(n)=phi(n+1), in C. Rivera's Primepuzzles.
Kevin Ford, Solutions of phi(n) = phi(n+k) and sigma(n) = sigma(n + k), arXiv:2002.12155 [math.NT], 2020.

Cf. A000010, A001274, A001494, A179186, A179187, A179188, A007015.

[n: n in [1..100000] | EulerPhi(n) eq EulerPhi(n+7)]; // Vincenzo Librandi, Sep 08 2016

Select[Range[100000], EulerPhi[#] == EulerPhi[# + 7] &] (* Vincenzo Librandi, Sep 08 2016 *)

{op=vector(N=7); for( n=1, 1e5, if( op[n%N+1]+0==op[n%N+1]=eulerphi(n), print1(n-N, ", ")))}

A000010(a(n)) = A000010(a(n)+7).

A179202 Numbers n such that phi(n) = phi(n+8), with Euler's totient function phi=A000010.

Original entry on oeis.org

13, 16, 19, 25, 28, 32, 40, 70, 104, 128, 175, 182, 209, 280, 296, 488, 551, 584, 657, 715, 806, 910, 1232, 1256, 1544, 1602, 2022, 2048, 2216, 2288, 2504, 2540, 2590, 2717, 2912, 3176, 3368, 3640, 3656, 4060, 4328, 4904, 5246, 5288, 5320, 5384, 5864, 5969

Offset: 1

M. F. Hasler, Jan 05 2011

nonn

Among the 5596 terms below 10^7, a(6)=32 is the only term such that a(n+1) = a(n)+8.
There are 141741552 terms under 10^12. - Jud McCranie, Feb 13 2012
If a(n) is even then a(n)/2 is in A179186 - see comment at A217139. - Jud McCranie, Dec 31 2012

M. F. Hasler and Jud McCranie, Table of n, a(n) for n = 1..10000 (first 5596 terms from M. F. Hasler)
F. Firoozbakht, Puzzle 466. phi(n-1)=phi(n)=phi(n+1), in C. Rivera's Primepuzzles.
Kevin Ford, Solutions of phi(n)=phi(n+k) and sigma(n)=sigma(n+k), arXiv:2002.12155 [math.NT], 2020.

Cf. A000010, A001274, A001494, A179186, A179187, A179188, A179189, A007015.

[n: n in [1..10000] | EulerPhi(n) eq EulerPhi(n+8)]; // Vincenzo Librandi, Sep 08 2016

Select[Range[6000], EulerPhi[#] == EulerPhi[# + 8] &] (* Vincenzo Librandi, Sep 08 2016 *)

{op=vector(N=8); for( n=1, 1e4, if( op[n%N+1]+0==op[n%N+1]=eulerphi(n), print1(n-N, ", ")))}

A000010(a(n)) = A000010(a(n)+8).

Previous Showing 101-110 of 4245 results. Next

cp's OEIS Frontend

A079124 Number of ways to partition n into distinct positive integers <= phi(n), where phi is Euler's totient function (A000010).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A082061 Greatest common prime divisor of n and phi(n)=A000010(n); a(n)=1 if no common prime divisor exists.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A082065 Greatest common prime-divisor of phi(n)=A000010(n) and sigma(2,n) = A001157(n); a(n) = 1 if no common prime-divisor exists.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A082067 Smallest prime that divides n and phi(n)=A000010(n), or 1 if n and phi(n) are relatively prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A098189 Sum of unitary divisors minus Euler phi: a(n) = A034448(n) - A000010(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A110086 Numbers k such that sigma(k) - phi(k) <= tau(k)^omega(k), where sigma = A000203, phi = A000010, tau = A000005 and omega = A001221.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A147619 Numbers n = concat(a,b) such that phi(n) = phi(a) * phi(b), where phi = A000010.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs