|
%I #19 Sep 11 2019 22:51:48
%S 0,1,2,3,4,17,18,23,92,93,118,467,468,593,2342,2343,2968,11717,11718,
%T 14843,58592,58593,74218,292967,292968,371093,1464842,1464843,1855468,
%U 7324217,7324218,9277343,36621092,36621093,46386718,183105467
%N Shortest partition of n with maximal product, sorted descending & considered as a base-5 number.
%H Alois P. Heinz, <a href="/A178683/b178683.txt">Table of n, a(n) for n = 0..1000</a>
%H E. W. Dijkstra, EWD Archive <a href="http://userweb.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EWD1044.html">To hell with "meaningful identifiers" - EWD1044</a>
%H Roger Hui & Boyko Bantchev, J Wiki <a href="http://www.jsoftware.com/jwiki/Essays/Partitions">An Essay on Partitions</a>
%e 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.
%e 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.
%e 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.
%p a:= proc(n) local m, q, r;
%p if n<5 then n
%p else q:= iquo(n,3,'r');
%p m:= 3*(5^q-1)/4;
%p if r=1 then m:= m +5^(q-1)
%p elif r=2 then m:= m *5+2
%p fi; m
%p fi
%p end:
%p seq(a(n), n=0..35); # _Alois P. Heinz_, Nov 26 2010
%o (J)
%o . aXXXX =: (5 #. ] {::~ [: (i. >./) */&>)@:part"0
%o . part =: 3 : 'final (, new)^:y <<i.1 0' NB. Here & below due to Hui
%o . final=: ; @: (<@-.&0"1&.>) @ > @ {:
%o . new =: (-i.)@# <@:(cat&.>) ]
%o . cat =: [ ;@:(,.&.>) -@(<.#) {. ]
%K base,easy,nonn
%O 0,3
%A Dan Bron (dan(AT)bron.us), Jun 03 2010
|
