A366471 -id:A366471 - cp's OEIS frontend

A078651 Number of increasing geometric-progression subsequences of [1,...,n] with integral successive-term ratio and length >= 1.

1, 3, 5, 9, 11, 15, 17, 23, 27, 31, 33, 40, 42, 46, 50, 59, 61, 68, 70, 77, 81, 85, 87, 97, 101, 105, 111, 118, 120, 128, 130, 141, 145, 149, 153, 165, 167, 171, 175, 185, 187, 195, 197, 204, 211, 215, 217, 231, 235, 242, 246, 253, 255, 265, 269, 279, 283, 287

Offset: 1

Robert E. Sawyer (rs.1(AT)mindspring.com), Jan 08 2003

The number of geometric-progression subsequences of [1,...,n] with integral successive-term ratio r and length k is floor(n/r^(k-1))(n > 0, r > 1, k > 0).

			a(1): [1]; a(2): [1],[2],[1,2]; a(3): [1],[2],[3],[1,2],[1,3].

Paolo Xausa, Table of n, a(n) for n = 1..10000

a(n) = n + A078632(n).
See A366471 for rational ratios.
See A078567 for APs.
Partial sums of A169594.

g := (n, b) -> local i; add(iquo(n, b^i), i = 1..floor(log(n, b))):
a := n -> local b; n + add(g(n, b), b = 2..n):
seq(a(n), n = 1..58);  # Peter Luschny, Apr 03 2025

Accumulate[1 + Table[Total[IntegerExponent[n, Rest[Divisors[n]]]], {n, 100}]] (* Paolo Xausa, Aug 27 2025 *)

A078651(n) = {my(s=0, k=2); while(k<=n, s+=(n - sumdigits(n, k))/(k-1); k=k+1); n + s} \\ Zhuorui He, Aug 28 2025

a(n) = n + Sum_{r > 1, j > 0} floor(n/r^j).

A051336 Number of increasing arithmetic progressions in {1,2,3,...,n}, including trivial arithmetic progressions of lengths 1 and 2.

Original entry on oeis.org

1, 3, 7, 13, 22, 33, 48, 65, 86, 110, 138, 168, 204, 242, 284, 330, 381, 434, 493, 554, 621, 692, 767, 844, 929, 1017, 1109, 1205, 1307, 1411, 1523, 1637, 1757, 1881, 2009, 2141, 2282, 2425, 2572, 2723, 2882, 3043, 3212, 3383, 3560, 3743, 3930, 4119

Offset: 1

John W. Layman, Nov 02 1999

The number of arithmetic subsequences of [1, ..., n] with successive-term increment i and length k is (n-i*(k-1))(i > 0, k > 0, n > i*(k-1)). - Robert E. Sawyer (rs.1(AT)mindspring.com)

The best algorithm known for generating a(n) from scratch has order O(sqrt(n)) (see below). If a(n-1) is known, it reduces to O(n^(1/3)). - Daniel Hoying, May 20 2020

			a(1): [1];
a(2): [1],[2],[1,2];
a(3): [1],[2],[3],[1,2],[1,3],[2,3],[1,2,3].

T. D. Noe, Table of n, a(n) for n = 1..1000
Marcel K. Goh, Jad Hamdan, and Jonah Saks, The lattice of arithmetic progressions, arXiv:2106.05949 [math.CO], 2021.
Daniel Hoying, Proof of recurrence relation, May 19 2020.

Cf. A078567.
Cf. A006218, A143127.
See A078651 and A366471 for GPs.

nmax = 48; t = Table[ DivisorSigma[0, n], {n, 1, nmax}]; Accumulate[ Accumulate[t]+1] - Accumulate[t] (* Jean-François Alcover, Nov 08 2011 *)
With[{c=Accumulate[DivisorSigma[0,Range[50]]]},Accumulate[c+1]-c] (* Harvey P. Dale, Dec 23 2015 *)
nmax = 50; RecurrenceTable[{a[n] == a[n-1]+1+p[n], p[n] == p[n-1]+DivisorSigma[0, n-1], a[1] == 1, p[1] == 0}, {a, p}, {n, 1, nmax}][[All,1]] (* Daniel Hoying, May 16 2020 *)

from math import isqrt
def A051336(n): return (((s:=isqrt(n-1))*(s+1))**2>>2)+(1-s**2)*n+sum((q:=(n-1)//k)*(2*n-k*(1+q)) for k in range(1, s+1)) # Chai Wah Wu, Oct 21 2023

Theorem: the second differences give tau(n+1), the number of divisors of n+1 (A000005).
a(n) = n + A078567(n).
a(n) = n + Sum_{ i=1..n-1, j=1..floor(n/i) } (n - i*j). - Robert E. Sawyer (rs.1(AT)mindspring.com)
From Daniel Hoying, May 15 2020: (Start)
a(n+1) = a(n) + 1 + Sum_{i=1..n} tau(i).
       = a(n) + 1 + A006218(n+1).
a(n+1) = (n + 1)*(1 + Sum_{i=1..n} floor(n/i)) - Sum_{i=1..n} i*tau(i).
       = (n + 1)*(1 + A006218(n)) - A143127(n). (End)

A365677 Number of increasing geometric progressions in {1,2,3,...,n} with rational ratio and length >= 3.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 1, 3, 5, 5, 5, 6, 6, 6, 6, 11, 11, 13, 13, 14, 14, 14, 14, 16, 20, 20, 24, 25, 25, 25, 25, 31, 31, 31, 31, 36, 36, 36, 36, 38, 38, 38, 38, 39, 41, 41, 41, 46, 52, 56, 56, 57, 57, 61, 61, 63, 63, 63, 63, 64, 64, 64, 66, 79, 79, 79, 79, 80, 80, 80, 80, 86, 86, 86, 90, 91, 91

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Oct 23 2023

nonn

			a(9) = 5 as {1,2,...,9} contains the geometric progressions [1,2,4], [1,2,4,8], [2,4,8], [1,3,9], [4,6,9].

Scott R. Shannon, Table of n, a(n) for n = 1..1000

Cf. A366471, A078651, A051336.

a(n) = A366471(n) - n*(1 + (n-1)/2) = Sum_{k=3 .. 1+floor(log_2(n))} Sum_{p=2..floor(n^(1/(k-1)))} phi(p)*floor(n/p^(k-1)), where phi is the Euler phi-function A000010.

A366472 Irregular triangle read by rows: T(n,k) (n >= 1, k >= 1) = number of increasing geometric progressions in {1,2,3,...,n} of length k with rational ratio.

Original entry on oeis.org

1, 2, 1, 3, 3, 4, 6, 1, 5, 10, 1, 6, 15, 1, 7, 21, 1, 8, 28, 2, 1, 9, 36, 4, 1, 10, 45, 4, 1, 11, 55, 4, 1, 12, 66, 5, 1, 13, 78, 5, 1, 14, 91, 5, 1, 15, 105, 5, 1, 16, 120, 8, 2, 1, 17, 136, 8, 2, 1, 18, 153, 10, 2, 1, 19, 171, 10, 2, 1, 20, 190, 11, 2, 1, 21, 210, 11, 2, 1, 22, 231, 11, 2, 1, 23, 253, 11, 2, 1, 24, 276, 12, 3, 1

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Oct 23 2023

			Triangle begins:
  [1],
  [2, 1],
  [3, 3],
  [4, 6, 1],
  [5, 10, 1],
  [6, 15, 1],
  [7, 21, 1],
  [8, 28, 2, 1],
  [9, 36, 4, 1],
  [10, 45, 4, 1],
  [11, 55, 4, 1],
  [12, 66, 5, 1],
  [13, 78, 5, 1],
  [14, 91, 5, 1],
  [15, 105, 5, 1],
  [16, 120, 8, 2, 1],
...

Row sums give A366471.
First three columns are A000027, A000217, A132345.
Cf. A000010.

with(numtheory);
A366472 := proc(n) local v,u2,u1,k,i,p;
v := Array(1..100, 0);
v[1] := n;
u1 := 1+floor(log(n)/log(2));
for k from 2 to u1 do
   u2 := floor(n^(1/(k-1)));
   v[k] := add(phi(p)*floor(n/p^(k-1)),p=2..u2);
  od;
[seq(v[i],i=1..u1)];
end;
for n from 1 to 36 do lprint(A366472(n)); od:

T(n,k) = Sum_{p=2..floor(n^(1/(k-1)))} phi(p)*floor(n/p^(k-1)) where phi is the Euler phi-function A000010 and k runs from 1 to 1+floor(log_2(n)).

A381886 Triangle read by rows: T(n, k) = Sum_{j=1..floor(log[k](n))} floor(n / k^j) if k >= 2, T(n, 1) = n, T(n, 0) = 0^n.

Original entry on oeis.org

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

Offset: 0

Peter Luschny, Apr 03 2025

			Triangle starts:
  [ 0] 1;
  [ 1] 0,  1;
  [ 2] 0,  2,  1;
  [ 3] 0,  3,  1, 1;
  [ 4] 0,  4,  3, 1, 1;
  [ 5] 0,  5,  3, 1, 1, 1;
  [ 6] 0,  6,  4, 2, 1, 1, 1;
  [ 7] 0,  7,  4, 2, 1, 1, 1, 1;
  [ 8] 0,  8,  7, 2, 2, 1, 1, 1, 1;
  [ 9] 0,  9,  7, 4, 2, 1, 1, 1, 1, 1;
  [10] 0, 10,  8, 4, 2, 2, 1, 1, 1, 1, 1;
  [11] 0, 11,  8, 4, 2, 2, 1, 1, 1, 1, 1, 1;
  [12] 0, 12, 10, 5, 3, 2, 2, 1, 1, 1, 1, 1, 1;

Jeffrey C. Lagarias and Wijit Yangjit, The factorial function and generalizations, extended, arXiv:2310.12949 [math.NT], 2023.
A. M. Oller-Marcen and J. Maria Grau, On the Base-b Expansion of the Number of Trailing Zeros of b^k!, J. Int. Seq. 14 (2011) 11.6.8.

Cf. A011371 (column 2), A054861 (column 3), A054893 (column 4), A027868 (column 5), A054895 (column 6), A054896 (column 7), A054897 (column 8), A054898 (column 9), A078651 (row sums).

Cf. A078632, A078567, A153216, A366471.

T := (n, b) -> local i; ifelse(b = 0, b^n, ifelse(b = 1, n, add(iquo(n, b^i), i = 1..floor(log(n, b))))): seq(seq(T(n, b), b = 0..n), n = 0..12);
# Alternative:
T := (n, k) -> local j; ifelse(k = 0, k^n, ifelse(k = 1, n, add(padic:-ordp(j, k), j = 1..n))): for n from 0 to 12 do seq(T(n, k), k = 0..n) od;

T[n_, 0] := If[n == 0, 1, 0]; T[n_, 1] := n;
T[n_, k_] := Last@Accumulate[IntegerExponent[Range[n], k]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // MatrixForm
(* Alternative: *)
T[n_, k_] := Sum[Floor[n/k^j], {j, Floor[Log[k, n]]}]; T[n_, 1] := n; T[n_, 0] := 0^n; T[0, 0] = 1; Flatten@ Table[T[n, k], {n, 0, 12}, {k, 0, n}] (* Michael De Vlieger, Apr 03 2025 *)

T(n,k) = if (n==0, 1, if (n==1, k, if (k==0, 0, if (k==1, n, sum(j=1, n, valuation(j, k))))));
row(n) = vector(n+1, k, T(n,k-1)); \\ Michel Marcus, Apr 04 2025

from math import log
def T(n: int, b: int) -> int:
    return (b**n if b == 0 else n if b == 1 else
        sum(n // (b**i) for i in range(1, 1 + int(log(n, b)))))
print([[T(n, b) for b in range(n+1)] for n in range(12)])

def T(n, b): return (b^n if b == 0 else n if b == 1 else sum(valuation(j, b) for j in (1..n)))
print(flatten([[T(n, b) for b in range(n+1)] for n in srange(13)]))

T(n, k) = Sum_{j=1..n} valuation(j, k) for n >= 2.

cp's OEIS Frontend

A078651 Number of increasing geometric-progression subsequences of [1,...,n] with integral successive-term ratio and length >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A051336 Number of increasing arithmetic progressions in {1,2,3,...,n}, including trivial arithmetic progressions of lengths 1 and 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A365677 Number of increasing geometric progressions in {1,2,3,...,n} with rational ratio and length >= 3.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A366472 Irregular triangle read by rows: T(n,k) (n >= 1, k >= 1) = number of increasing geometric progressions in {1,2,3,...,n} of length k with rational ratio.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Formula

A381886 Triangle read by rows: T(n, k) = Sum_{j=1..floor(log[k](n))} floor(n / k^j) if k >= 2, T(n, 1) = n, T(n, 0) = 0^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

SageMath

Formula