A066032 Number of ways to write n as a product with no factor larger than m (1 <= m <=n, written row by row).

1, 0, 1, 0, 0, 1, 0, 1, 1, 2, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 2, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 2, 2, 2, 2, 3, 0, 0, 1, 1, 1, 1, 1, 1, 2, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 2, 2, 3, 3, 3, 3, 3, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2

Offset: 1

Author

Ulrich Schimke (ulrschimke(AT)aol.com), Feb 11 2002

Keywords

• nonn
• look
• tabl

Examples

			T(12, 5) = a(71) = 2, since there are 2 possibilities to write 12 as a product with no factor larger than 5 (4*3 and 3*2*2)
1;
0,1;
0,0,1;
0,1,1,2;
0,0,0,0,1;
0,0,1,1,1,2;
0,0,0,0,0,0,1;
0,1,1,2,2,2,2,3;
0,0,1,1,1,1,1,1,2;
0,0,0,0,1,1,1,1,1,2;
0,0,0,0,0,0,0,0,0,0,1;
0,0,1,2,2,3,3,3,3,3,3,4;
		

Links

• Reinhard Zumkeller, Rows n = 1..150 of triangle, flattened

Crossrefs

A001055(n) = T(n, n) is the right diagonal.

Programs

Haskell

a066032 1 1 = 1
a066032 n k = fromEnum (n <= k) +
   (sum $ map (\d -> a066032 (n `div` d) d) $
              takeWhile (<= k) $ tail $ a027751_row n)
a066032_row n = map (a066032 n) [1..n]
a066032_tabl = map a066032_row [1..]
-- Reinhard Zumkeller, Oct 01 2012

Maple

with(numtheory): T := proc(n::integer, m::integer) local i, A, summe, d: if isprime(n) then: if n <= m then RETURN(1) fi: RETURN(0): fi:
A := divisors(n) minus {n,1}: for d in A do: if d > m then A := A minus {d}: fi: od: summe := 0: for d in A do: summe := summe + T(n/d,d): od: if n <=m then summe := summe + 1: fi: RETURN(summe): end: A066032 := [seq(seq(T(n, m),m=1..n), n=1..16)];

Mathematica

T[1, 1] = 1; T[p_?PrimeQ, m_] := Boole[p <= m]; T[n_, m_] := Sum[T[n/d, d]* Boole[d <= m], {d, Divisors[n][[2 ;; -2]]}] + Boole[n <= m];
Table[T[n, m], {n, 1, 14}, {m, 1, n}] // Flatten (* Jean-François Alcover, Mar 01 2019 *)

Python

from sympy import divisors, isprime
def T(n, m):
    if isprime(n): return 1 if n<=m else 0
    A=(d for d in divisors(n)[1:-1] if d <= m)
    s=sum(T(n//d, d) for d in A)
    return s + 1 if n<=m else s
for n in range(1, 21): print([T(n, m) for m in range(1, n + 1)]) # Indranil Ghosh, Aug 19 2017

Formula

T(1, 1) = 1. For every prime p T(p, m) = 1 if p <= m and 0 else. For composite n: T(n, m) = sum[T(n/d, d)] + I(n<=m) where the sum is over all divisors d of n except 1 and n with d <= m and I(n<=m) is 1 if n<=m and 0 else.

From Reinhard Zumkeller, Oct 01 2012: (Start)

T(n,floor(n/2)) = A028422(n) for n > 1; T(n,floor(n/3)) = A216599(n) for n > 2;

T(n,floor(n/4)) = A216600(n) for n > 3; T(n,floor(n/5)) = A216601(n) for n > 4;

T(n,floor(n/6)) = A216602(n) for n > 5. (End)