A078632 Number of geometric subsequences of [1,...,n] with integral successive-term ratio and length > 1.

0, 1, 2, 5, 6, 9, 10, 15, 18, 21, 22, 28, 29, 32, 35, 43, 44, 50, 51, 57, 60, 63, 64, 73, 76, 79, 84, 90, 91, 98, 99, 109, 112, 115, 118, 129, 130, 133, 136, 145, 146, 153, 154, 160, 166, 169, 170, 183, 186, 192, 195, 201, 202, 211, 214, 223, 226, 229, 230, 242

Offset: 1

Author

Robert E. Sawyer (rs.1(AT)mindspring.com)

Keywords

• nonn
• easy
• changed

Comments

The number of geometric 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).

Examples

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

Links

• Zhuorui He, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A078651.

Row sums of triangle A090623.

Partial sums of A309891.

Programs

Maple

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

Mathematica

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

PARI

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

Formula

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