A072031 -id:A072031 - cp's OEIS frontend

A055507 a(n) = Sum_{k=1..n} d(k)*d(n+1-k), where d(k) is number of positive divisors of k.

1, 4, 8, 14, 20, 28, 37, 44, 58, 64, 80, 86, 108, 108, 136, 134, 169, 160, 198, 192, 236, 216, 276, 246, 310, 288, 348, 310, 400, 344, 433, 396, 474, 408, 544, 450, 564, 512, 614, 522, 688, 560, 716, 638, 756, 636, 860, 676, 859, 772, 926, 758, 1016, 804, 1032

Offset: 1

Leroy Quet, Jun 29 2000

nonn

a(n) is the number of ordered ways to express n+1 as a*b+c*d with 1 <= a,b,c,d <= n. - David W. Wilson, Jun 16 2003
tau(n) (A000005) convolved with itself, treating this result as a sequence whose offset is 2. - Graeme McRae, Jun 06 2006
Convolution of A341062 and nonzero terms of A006218. - Omar E. Pol, Feb 16 2021

			a(4) = d(1)*d(4) + d(2)*d(3) + d(3)*d(2) + d(4)*d(1) = 1*3 +2*2 +2*2 +3*1 = 14.
3 = 1*1+2*1 in 4 ways, so a(2)=4; 4 = 1*1+1*3 (4 ways) = 2*1+2*1 (4 ways), so a(3)=8; 5 = 4*1+1*1 (4 ways) = 2*2+1*1 (2 ways) + 3*1+2*1 (8 ways), so a(4) = 14. - _N. J. A. Sloane_, Jul 07 2012

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
George E. Andrews, Stacked lattice boxes, Ann. Comb. 3 (1999), 115-130. See D_{0,0}.
A. E. Ingham, Some asymptotic formulae in the theory of numbers, Journal of the London Mathematical Society, Vol. s1-2, No. 3 (1927), pp. 202-208.
Yoichi Motohashi, The binary additive divisor problem, Annales scientifiques de l'École Normale Supérieure, Sér. 4, 27 no. 5 (1994), p. 529-572.
E. C. Titchmarsh, Some problems in the analytic theory of numbers, The Quarterly Journal of Mathematics 1 (1942): 129-152.

Cf. A000005, A000385, A072031, A212151.

Cf. A006218, A341062.

with(numtheory); A055507:=n->add(tau(j)*tau(n+1-j),j=1..n);

Table[Sum[DivisorSigma[0, k]*DivisorSigma[0, n + 1 - k], {k, 1, n}], {n, 1, 100}] (* Vaclav Kotesovec, Aug 08 2022 *)

a(n)=sum(k=1,n,numdiv(k)*numdiv(n+1-k)) \\ Charles R Greathouse IV, Oct 17 2012

from sympy import divisor_count
def A055507(n): return  (sum(divisor_count(i+1)*divisor_count(n-i) for i in range(n>>1))<<1)+(divisor_count(n+1>>1)**2 if n&1 else 0) # Chai Wah Wu, Jul 26 2024

G.f.: Sum_{i >= 1, j >= 1} x^(i+j-1)/(1-x^i)/(1-x^j). - Vladeta Jovovic, Nov 11 2001
Working with an offset of 2, it appears that the o.g.f is equal to the Lambert series sum {n >= 2} A072031(n-1)*x^n/(1 - x^n). - Peter Bala, Dec 09 2014
a(n) = A212151(n+2) - A212151(n+1). - Ridouane Oudra, Sep 12 2020

More terms from James Sellers, Jul 04 2000

Definition clarified by N. J. A. Sloane, Jul 07 2012

A072030 Array read by antidiagonals: T(n,k) = number of steps in simple Euclidean algorithm for gcd(n,k) where n >= 1, k >= 1.

Original entry on oeis.org

1, 2, 2, 3, 1, 3, 4, 3, 3, 4, 5, 2, 1, 2, 5, 6, 4, 4, 4, 4, 6, 7, 3, 4, 1, 4, 3, 7, 8, 5, 2, 5, 5, 2, 5, 8, 9, 4, 5, 3, 1, 3, 5, 4, 9, 10, 6, 5, 5, 6, 6, 5, 5, 6, 10, 11, 5, 3, 2, 5, 1, 5, 2, 3, 5, 11, 12, 7, 6, 6, 5, 7, 7, 5, 6, 6, 7, 12, 13, 6, 6, 4, 6, 4, 1, 4, 6, 4, 6, 6, 13, 14, 8, 4, 6, 2, 3, 8, 8, 3, 2, 6, 4, 8, 14

Offset: 1

Michael Somos, Jun 07 2002

The old definition was: Triangle T(a,b) read by rows giving number of steps in simple Euclidean algorithm for gcd(a,b) (a > b >= 1). [For this, see A049834.]
For example <11,3> -> <8,3> -> <5,3> -> <3,2> -> <2,1> -> <1,1> -> <1,0> takes 6 steps.
The number of steps function can be defined inductively by T(a,b) = T(b,a), T(a,0) = 0, and T(a+b,b) = T(a,b)+1.
The simple Euclidean algorithm is the Euclidean algorithm without divisions. Given a pair  of positive integers with a>=b, let  = . This is iterated until a^(m)=0. Then T(a,b) is the number of steps m.
Note that row n starts at k = 1; the number of steps to compute gcd(n,0) or gcd(0,n) is not shown. - T. D. Noe, Oct 29 2007

			The array begins:
   1,  2,  3,  4,  5,  6,  7,  8,  9, 10, ...
   2,  1,  3,  2,  4,  3,  5,  4,  6,  5, ...
   3,  3,  1,  4,  4,  2,  5,  5,  3,  6, ...
   4,  2,  4,  1,  5,  3,  5,  2,  6,  4, ...
   5,  4,  4,  5,  1,  6,  5,  5,  6,  2, ...
   6,  3,  2,  3,  6,  1,  7,  4,  3,  4, ...
   7,  5,  5,  5,  5,  7,  1,  8,  6,  6, ...
   8,  4,  5,  2,  5,  4,  8,  1,  9,  5, ...
   9,  6,  3,  6,  6,  3,  6,  9,  1, 10, ...
  10,  5,  6,  4,  2,  4,  6,  5, 10,  1, ...
  ...
The first few antidiagonals are:
   1;
   2,  2;
   3,  1,  3;
   4,  3,  3,  4;
   5,  2,  1,  2,  5;
   6,  4,  4,  4,  4,  6;
   7,  3,  4,  1,  4,  3,  7;
   8,  5,  2,  5,  5,  2,  5,  8;
   9,  4,  5,  3,  1,  3,  5,  4,  9;
  10,  6,  5,  5,  6,  6,  5,  5,  6, 10;
  ...

T. D. Noe, Antidiagonals 1..49, flattened
James C. Alexander, The Entropy of the Fibonacci Code (1989).

Antidiagonal sums are A072031.
Cf. A049834 (the lower left triangle), A003989, A050873.
See also A267177, A267178, A267181.

A072030 := proc(n,k)
    option remember;
    if n < 1 or k < 1 then
        0;
    elif n = k then
        1 ;
    elif n < k then
        procname(k,n) ;
    else
        1+procname(k,n-k) ;
    end if;
end proc:
seq(seq(A072030(d-k,k),k=1..d-1),d=2..12) ; # R. J. Mathar, May 07 2016
# second Maple program:
A:= (n, k)-> add(i, i=convert(k/n, confrac)):
seq(seq(A(n, 1+d-n), n=1..d), d=1..14);  # Alois P. Heinz, Jan 31 2023

T[n_, k_] := T[n, k] = Which[n<1 || k<1, 0, n==k, 1, nJean-François Alcover, Nov 21 2016, adapted from PARI *)

T(n, k) = if( n<1 || k<1, 0, if( n==k, 1, if( n

Definition and Comments revised by N. J. A. Sloane, Jan 14 2016

cp's OEIS Frontend

A055507 a(n) = Sum_{k=1..n} d(k)*d(n+1-k), where d(k) is number of positive divisors of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions