A045545 -id:A045545 - cp's OEIS frontend

A143656 Triangle T(n, k) = A045545(k) if gcd(n,k) = 1, 0 otherwise, read by rows.

1, 1, 0, 1, 1, 0, 1, 0, 2, 0, 1, 1, 2, 3, 0, 1, 0, 0, 0, 7, 0, 1, 1, 2, 3, 7, 8, 0, 1, 0, 2, 0, 7, 0, 22, 0, 1, 1, 0, 3, 7, 0, 22, 32, 0, 1, 0, 2, 0, 0, 0, 22, 0, 66, 0, 1, 1, 2, 3, 7, 8, 22, 32, 66, 91, 0, 1, 0, 0, 0, 7, 0, 22, 0, 0, 0, 233, 0, 1, 1, 2, 3, 7, 8, 22, 32, 66, 91, 233, 263, 0

Offset: 1

Gary W. Adamson, Aug 28 2008

Sum of row terms = A045545 starting with offset 1: (1, 1, 2, 3, 7, 8, 22,...).
A045545 also = rightmost diagonal with nonzero terms.
Sum of n-th row terms = rightmost nonzero term of next row.
Prime n rows = first (n-1) terms of (1, 1, 2, 3, 7, 8,...) followed by 0.
Asymptotic limit of A054521^n * A143656 = A045545 as a vector.

			First few rows of the triangle =
  1;
  1, 0;
  1, 1, 0;
  1, 0, 2, 0;
  1, 1, 2, 3, 0;
  1, 0, 0, 0, 7, 0;
  1, 1, 2, 3, 7, 8,  0;
  1, 0, 2, 0, 7, 0, 22,  0;
  1, 1, 0, 3, 7, 0, 22, 32,  0;
  1, 0, 2, 0, 0, 0, 22,  0, 66, 0;
  ...

G. C. Greubel, Rows n = 1..50 of the triangle, flattened

Cf. A045545, A054521.

A045545:= n->`if`(n<3, 1, add(`if`(gcd(n,j)=1, A045545(j), 0), j=1..n-1) );
T:= (n,k) -> `if`(gcd(n,k)=1, A045545(k), 0);
seq(seq(T(n,k), k=1..n), n=1..12); # G. C. Greubel, Mar 08 2021

A045545[n_]:= A045545[n]= If[n<3, 1, Sum[Boole[GCD[n, k]==1] A045545[k], {k,n-1}]];
T[n_, k_]:= If[GCD[n, k]==1, A045545[k], 0];
Table[T[n, k], {n,12}, {k,n}]//Flatten (* G. C. Greubel, Mar 08 2021 *)

@CachedFunction
def A045545(n): return 1 if n<3 else sum( kronecker_delta(gcd(n, j), 1)*A045545(j) for j in (0..n-1) )
def T(n,k): return A045545(k) if gcd(n,k)==1 else 0
flatten([[T(n,k) for k in (1..n)] for n in (1..12)]) # G. C. Greubel, Mar 08 2021

Triangle read by rows, A054521 * (A045545 * 0^(n-k)); 1<=k<=n.

T(n,k) = A045545(k) if gcd(n,k) = 1, 0 otherwise, where A045545 = (1, 1, 2, 3, 7, 8, 22, 32, 66,...) starting with offset 1.

A118418 Erroneous version of A045545.

Original entry on oeis.org

1, 1, 2, 4, 8, 9, 25, 36, 75, 103, 264, 298, 826, 1176, 2333

Offset: 1

dead

A023896 Sum of positive integers in smallest positive reduced residue system modulo n. a(1) = 1 by convention.

Original entry on oeis.org

1, 1, 3, 4, 10, 6, 21, 16, 27, 20, 55, 24, 78, 42, 60, 64, 136, 54, 171, 80, 126, 110, 253, 96, 250, 156, 243, 168, 406, 120, 465, 256, 330, 272, 420, 216, 666, 342, 468, 320, 820, 252, 903, 440, 540, 506, 1081, 384, 1029, 500, 816, 624, 1378, 486, 1100, 672

Offset: 1

Olivier Gérard

Sum of totatives of n, i.e., sum of integers up to n and coprime to n.
a(1) = 1, since 1 is coprime to any positive integer.
Row sums of A038566. - Wolfdieter Lang, May 03 2015
Islam & Manzoor prove that a(n) is an injection for n > 1, see links. In other words, if a(m) = a(n), and min(m, n) > 1, then m = n. - Muhammed Hedayet, May 19 2024

			G.f. = x + x^2 + 3*x^3 + 4*x^4 + 10*x^5 + 6*x^6 + 21*x^7 + 16*x^8 + 27*x^9 + ...
a(12) = 1 + 5 + 7 + 11 = 24.
n = 40: The smallest positive reduced residue system modulo 40 is {1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39}. The sum is a(40) = 320. Average is 20.

Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 48, problem 16, the function phi_1(n).
David M. Burton, Elementary Number Theory, p. 171.
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 2001, p. 163.
J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, p. 111.

Michael De Vlieger, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
John D. Baum, A Number-Theoretic Sum, Mathematics Magazine 55.2 (1982): 111-113.
Geoffrey B. Campbell, Dirichlet summations and products over primes, Int. J. Math. Math. Sci. 16 92) (1993) 359. eq. (3.1)
Muhammed H. Islam and Shahriar Manzoor, φ1 and phitorial are injections, for any positive integer N, where N > 1.
Constantin M. Petridi, The Sums of the k-powers of the Euler set and their connection with Artin's conjecture for primitive roots, arXiv:1612.07632 [math.NT], 2016.
David Zmiaikou, Origamis and permutation groups, Thesis, 2011. See p. 65.

Cf. A000010, A000203, A002180, A045545, A001783, A024816, A066760, A054521, A067392, A038566.
Row sums of A127368, A144734, A144824.
Cf. A000217, A002618, A008683, A009195, A023022, A065484, A076512, A175505, A175506.

a023896 = sum . a038566_row  -- Reinhard Zumkeller, Mar 04 2012

[1] cat [n*EulerPhi(n)/2: n in [2..70]]; // Vincenzo Librandi, May 16 2015

A023896 := proc(n)
    if n = 1 then
        1;
    else
        n*numtheory[phi](n)/2 ;
    end if;
end proc: # R. J. Mathar, Sep 26 2013

a[ n_ ] = n/2*EulerPhi[ n ]; a[ 1 ] = 1; Table[a[n], {n, 56}]
a[ n_] := If[ n < 2, Boole[n == 1], Sum[ k Boole[1 == GCD[n, k]], { k, n}]]; (* Michael Somos, Jul 08 2014 *)

{a(n) = if(n<2, n>0, n*eulerphi(n)/2)};

A023896(n)=n*eulerphi(n)\/2 \\ about 10% faster. - M. F. Hasler, Feb 01 2021

from sympy import totient
def A023896(n): return 1 if n == 1 else n*totient(n)//2 # Chai Wah Wu, Apr 08 2022

def A023896(n): return 1 if n == 1 else n*euler_phi(n)//2
print([A023896(n) for n in range(1, 57)])  # Peter Luschny, Dec 03 2023

a(n) = n*A023022(n) for n > 2.
a(n) = phi(n^2)/2 = n*phi(n)/2 = A002618(n)/2 if n > 1, a(1)=1. See the Apostol reference for this exercise.
a(n) = Sum_{1 <= k < n, gcd(k, n) = 1} k.
If n = p is a prime, a(p) = T(p-1) where T(k) is the k-th triangular number (A000217). - Robert G. Wilson v, Jul 31 2004
Equals A054521 * [1,2,3,...]. - Gary W. Adamson, May 20 2007
a(n) = A053818(n) * A175506(n) / A175505(n). - Jaroslav Krizek, Aug 01 2010
If m,n > 1 and gcd(m,n) = 1 then a(m*n) = 2*a(m)*a(n). - Thomas Ordowski, Nov 09 2014
G.f.: Sum_{n>=1} mu(n)*n*x^n/(1-x^n)^3, where mu(n) = A008683(n). - Mamuka Jibladze, Apr 24 2015
G.f. A(x) satisfies A(x) = x/(1 - x)^3 - Sum_{k>=2} k * A(x^k). - Ilya Gutkovskiy, Sep 06 2019
For n > 1: a(n) = (n*A076512(n)/2)*A009195(n). - Jamie Morken, Dec 16 2019
Sum_{n>=1} 1/a(n) = 2 * A065484 - 1 = 3.407713... . - Amiram Eldar, Oct 09 2023

Typos in programs corrected by Zak Seidov, Aug 03 2010

Name and example edited by Wolfdieter Lang, May 03 2015

A054251 a(0) = 1; a(n) = Sum_{0 <= k < n and gcd(k, n) != 1} a(k).

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 5, 1, 9, 7, 19, 1, 45, 1, 83, 79, 165, 1, 417, 1, 827, 639, 1575, 1, 3875, 927, 7025, 5069, 14689, 1, 35461, 1, 64199, 47175, 128399, 52727, 309767, 1, 566565, 409567, 1186863, 1, 2835257, 1, 5202425, 4888729, 10357675, 1, 26066615

Offset: 0

David W. Wilson

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A045545.

a[0]:= 1; a[n_]:= a[n] =Sum[If[GCD[k, n]!=1, a[k], 0], {k,0,n-1}];
Table[a[n], {n, 0, 50}] (* G. C. Greubel, Jul 31 2019 *)

a(n) = if(n==0, 1, sum(j=0,n-1, if(gcd(j,n)!=1, a(j), 0)));
vector(50, n, n--; a(n)) \\ G. C. Greubel, Jul 31 2019

A333613 a(1) = 1; thereafter a(n) = Sum_{k = 1..n} a(k/gcd(n,k)).

Original entry on oeis.org

1, 2, 4, 7, 15, 21, 51, 78, 158, 230, 568, 661, 1797, 2595, 5117, 7789, 19095, 21702, 59892, 81801, 171329, 258028, 630942, 713093, 1887828, 2776798, 5727675, 8335692, 20702970, 21420664, 62826604, 92041835, 189376593, 281410640, 656577018, 742729123, 2087788417

Offset: 1

Ilya Gutkovskiy, Mar 28 2020

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 1..3930
Vaclav Kotesovec, Plot of a(n)^(1/n) for n = 1..10000

Cf. A006874, A045545, A057661, A332791.

A333613:= proc(n) option remember;
if n<3 then n;
else add( A333613(lcm(n,j)/n), j = 1..n);
end if; end proc;
seq(A333613(n), n=1..40); # G. C. Greubel, Mar 08 2021

a[1] = 1; a[n_] := a[n] = Sum[a[k/GCD[n, k]], {k, n}]; Table[a[n], {n, 37}]
a[1] = 1; a[n_] := a[n] = Sum[Sum[If[GCD[k, d] == 1, a[k], 0], {k, d}], {d, Divisors[n]}]; Table[a[n], {n, 37}]

@CachedFunction
def A333613(n): return 1 if n==1 else sum( A333613(lcm(n, j)/n) for j in (1..n) )
[A333613(n) for n in (1..40)] # G. C. Greubel, Mar 08 2021

a(1) = 1; a(n) = Sum_{k = 1..n} a(lcm(n, k)/n).

a(1) = 1; a(n) = Sum_{d|n} Sum_{k = 1..d, gcd(d, k) = 1} a(k).

A070963 a(1) = 2; for n >= 2, n = Sum_{1<=k

Original entry on oeis.org

2, 1, 2, 0, 4, -2, 0, 2, 6, -4, 6, -4, -6, 10, 2, -2, 12, -10, -2, 8, 2, -4, 8, 4, -16, 8, 10, -8, 10, -8, -8, 14, 14, -26, 26, -14, -36, 42, 20, -22, 68, -66, -60, 14, -10, 60, 40, -74, -38, -66, 10, 134, 44, -98, -64, -54, 22, 156, 20, -18, -34, -240, 10, 256, 32, -18, -6, -144, -72, 226, 70, -68, -50, -184, 58, 236, 82

Offset: 1

Leroy Quet, May 16 2002

sign

			12 = a(1) + a(5) + a(7) + a(11) = 2 + 4 + 0 + 6 because 1, 5, 7 and 11 are the positive integers < 12 and relatively prime to 12.

Sean A. Irvine, Table of n, a(n) for n = 1..10000

Cf. A045545.

A307856 a(1) = a(2) = 1; a(n) = Sum_{1 < k < n, k not dividing n} a(k).

Original entry on oeis.org

1, 1, 1, 1, 3, 4, 10, 18, 37, 71, 146, 285, 577, 1143, 2293, 4570, 9160, 18277, 36597, 73118, 146301, 292466, 585079, 1169848, 2340003, 4679431, 9359402, 18717687, 37436529, 74870685, 149743743, 299482896, 598970235, 1197931456, 2395872060, 4791725527, 9583469660, 19166902722

Offset: 1

Ilya Gutkovskiy, May 01 2019

nonn

G. C. Greubel, Table of n, a(n) for n = 1..1000

Cf. A003238, A045545.

Second column of A155033.

a := proc(n) local j; option remember;
if n < 3 then 1;
else add(`if`(`mod`(n, j) <> 0, a(j), 0), j = 2 .. n - 1);
end if; end proc;
seq(a(n), n = 1..40); # G. C. Greubel, Mar 08 2021

a[n_] := a[n] = Sum[Boole[Mod[n, k] != 0] a[k], {k,n-1}]; a[1] = a[2] = 1; Table[a[n], {n, 1, 38}]
terms = 38; A[] = 0; Do[A[x] = x (1 + x) + A[x]/(1 - x) - Sum[A[x^k], {k, 1, terms}] + O[x]^(terms + 1) // Normal, terms + 1]; Rest[CoefficientList[A[x], x]]
a[n_] := a[n] = SeriesCoefficient[x (1 + x + 1/(1 - x) Sum[a[k] x^k (1 - x^(k - 1))/(1 - x^k), {k, 1, n - 1}]), {x, 0, n}]; Table[a[n], {n, 1, 38}]

@CachedFunction
def a(n):
    if n<3: return 1
    else: return sum( a(j) if n%j!=0 else 0 for j in (2..n-1) )
[a(n) for n in (1..40)] # G. C. Greubel, Mar 08 2021

G.f. A(x) satisfies: A(x) = x*(1 + x) + A(x)/(1 - x) - Sum_{k>=1} A(x^k).
G.f.: A(x) = Sum_{n>=1} a(n)*x^n = x * (1 + x + (1/(1 - x)) * Sum_{n>=1} a(n)*x^n*(1 - x^(n-1))/(1 - x^n)).
a(n) ~ c * 2^n, where c = 0.0697287852138897098746368547699891689134990049613293203832908827967121295... - Vaclav Kotesovec, May 06 2019

A308475 a(1) = 1; a(n) = Sum_{k=1..n-1, gcd(n,k) = 1} binomial(n,k)*a(k).

Original entry on oeis.org

1, 2, 9, 40, 315, 1896, 21651, 191360, 2546487, 28064080, 488517183, 5879603280, 124673371719, 1928346159572, 42684093159480, 754925802649360, 20289814995554811, 366300418631427144, 11352374441063693655, 250187625076714423520, 7774760839170720287739

Offset: 1

Ilya Gutkovskiy, May 29 2019

nonn

G. C. Greubel, Table of n, a(n) for n = 1..425

Cf. A000670, A045545, A052882, A056188.

a:= proc(n) option remember;
if n=1 then 1;
else add( `if`(gcd(n,j)=1, binomial(n,j)*a(j), 0), j=1..n-1);
end if; end proc;
seq(a(n), n = 1..30); # G. C. Greubel, Mar 08 2021

a[n_] := Sum[If[GCD[n, k] == 1, Binomial[n, k] a[k], 0], {k, 1, n - 1}]; a[1] = 1; Table[a[n], {n, 1, 21}]

@CachedFunction
def a(n):
    if n==1: return 1
    else: return sum( kronecker_delta(gcd(n,j), 1)*binomial(n,j)*a(j) for j in (1..n-1) )
[a(n) for n in (1..30)] # G. C. Greubel, Mar 08 2021

A308476 a(1) = 1; a(n) = Sum_{k=1..n-1, gcd(n,k) = 1} Stirling2(n,k)*a(k).

Original entry on oeis.org

1, 1, 4, 25, 366, 5491, 176569, 5332097, 276268942, 13470365431, 1135683784753, 75066413338423, 9256260956838520, 918768523598548169, 140268128758724744770, 18398287904991375995745, 3879391299475140314514162, 594721341754741064012714341

Offset: 1

Ilya Gutkovskiy, May 29 2019

nonn

G. C. Greubel, Table of n, a(n) for n = 1..250

Cf. A005121, A045545, A308463.

a := proc(n) local j; option remember;
if n = 1 then 1;
else add(`if`(gcd(n, j) = 1, Stirling2(n, j)*a(j), 0), j = 1 .. n - 1);
end if; end proc;
seq(a(n), n = 1 .. 30); # G. C. Greubel, Mar 08 2021

a[n_] := Sum[If[GCD[n, k] == 1, StirlingS2[n, k] a[k], 0], {k, 1, n - 1}]; a[1] = 1; Table[a[n], {n, 1, 18}]

@CachedFunction
def a(n):
    if n==1: return 1
    else: return sum( stirling_number2(n,j)*a(j) if gcd(n,j)==1 else 0 for j in (1..n-1) )
[a(n) for n in (1..30)] # G. C. Greubel, Mar 08 2021

A085086 a(1) = 1; if n is composite then a(n) = Sum_{i < n, i not prime} a(i), else if n is prime then a(n) = sum_{ j < n, j is a noncomposite} a(j).

Original entry on oeis.org

1, 1, 2, 1, 4, 2, 8, 4, 8, 16, 16, 32, 32, 64, 128, 256, 64, 512, 128, 1024, 2048, 4096, 256, 8192, 16384, 32768, 65536, 131072, 512, 262144, 1024, 524288, 1048576, 2097152, 4194304, 8388608, 2048, 16777216, 33554432, 67108864, 4096, 134217728, 8192

Offset: 1

Amarnath Murthy and Meenakshi Srikanth (menakan_s(AT)yahoo.com), Jul 02 2003

nonn

			a(7) = a(1) + a(2) + a(3) + a(5) = 8.

Cf. A002033, A045545.

a(p(i)) = 2^(i-1); a(A002808(i)) = 2^(i-1). - David Wasserman, Jan 25 2005

More terms from David Wasserman, Jan 25 2005

cp's OEIS Frontend

A143656 Triangle T(n, k) = A045545(k) if gcd(n,k) = 1, 0 otherwise, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A118418 Erroneous version of A045545.

Views

Author

Keywords

A023896 Sum of positive integers in smallest positive reduced residue system modulo n. a(1) = 1 by convention.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

SageMath

Formula

Extensions

A054251 a(0) = 1; a(n) = Sum_{0 <= k < n and gcd(k, n) != 1} a(k).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A333613 a(1) = 1; thereafter a(n) = Sum_{k = 1..n} a(k/gcd(n,k)).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A070963 a(1) = 2; for n >= 2, n = Sum_{1<=k

Views

Author

Keywords

Examples

Links

Crossrefs

A307856 a(1) = a(2) = 1; a(n) = Sum_{1 < k < n, k not dividing n} a(k).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A308475 a(1) = 1; a(n) = Sum_{k=1..n-1, gcd(n,k) = 1} binomial(n,k)*a(k).

Views

Author

Keywords