OFFSET
0,3
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
E. W. Dijkstra, EWD Archive To hell with "meaningful identifiers" - EWD1044
Roger Hui & Boyko Bantchev, J Wiki An Essay on Partitions
EXAMPLE
For n=10: the integer 10 has 42 partitions (e.g., 7+1+1+1, 6+4, 4+3+3, ...). The products of these partitions range from 1 (1*1*1*...) to 36.
There are only two partitions that have the maximal product of 36: (4,3,3) and (3,3,2,2). Of these, the former is shorter (3 elements vs 4). So 4,3,3 is the shortest maximal partition of 10.
This partition, sorted descending and considered as a number in base 5 (where each element of the partition is a digit), is (4*5^2) + (3*5^1) + (3*5^0) = 118. Hence a(10) = 118.
MAPLE
a:= proc(n) local m, q, r;
if n<5 then n
else q:= iquo(n, 3, 'r');
m:= 3*(5^q-1)/4;
if r=1 then m:= m +5^(q-1)
elif r=2 then m:= m *5+2
fi; m
fi
end:
seq(a(n), n=0..35); # Alois P. Heinz, Nov 26 2010
PROG
(J)
. aXXXX =: (5 #. ] {::~ [: (i. >./) */&>)@:part"0
. part =: 3 : 'final (, new)^:y <<i.1 0' NB. Here & below due to Hui
. final=: ; @: (<@-.&0"1&.>) @ > @ {:
. new =: (-i.)@# <@:(cat&.>) ]
. cat =: [ ; @:(, .&.>) -@(<.#) {. ]
CROSSREFS
KEYWORD
base,easy,nonn
AUTHOR
Dan Bron (dan(AT)bron.us), Jun 03 2010
STATUS
approved