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,10

Links

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

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)

Example

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;

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 *)

Prog

(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
(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

Crossrefs

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

Sequence in context: A127475 A086014 A025437 * A035187 A291147 A278929

Adjacent sequences: A066029 A066030 A066031 * A066033 A066034 A066035

Keyword

nonn,look,tabl

Author

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

Status

approved