[seqfan] Re: Question about A002577 (Number of partitions of 2^n into powers of 2)

[Prof. Dr. Alois Heinz]

Georgi Guninski schrieb:

>A002577(n)=A000123(2^(n-1))
>A000123 Number of binary partitions: number of partitions of 2n into
>powers of 2
>A000123(n)=A018819(2n)
>A018819  Binary partition function: number of partitions of n into
>powers of 2
>
>i am interested in the exponentially easier question if the binary
>partition function is efficiently computable (say for n about 2^100). if
>virtual memory storage is a problem one is allowed to do reduction
>modulo integer.
>  
>
The Maple program

g:= proc(b, n) option remember; local t; if b<0 then 0 elif b=0 or n=0 
then 1 elif b>=n then add (g(b-t, n) *binomial (n+1, t) *(-1)^(t+1), 
t=1..n+1) else g(b-1, n) +g(2*b, n-1) fi end: a:= proc(n) local t; if 
irem(n,2)=1 then a(n-1) else t:= nops (convert (n, base, 2)); g(n /2^t, 
t) fi end: seq (a(n), n=0..20);

will also compute a(2^100) = 
142765966869976843710660982258955636134831621048779137900426673783847412905354719942512655856623622635990128615493072222411845826291713655869352187555785033042450356815565747370607928814850324885818520561386768253743950629988669405819352655877570777908150220979435189853852425692915287524901582144497657736448832507052842706276923135750640688797503135834490917270836987133677001886347199001023688688421123930484590497825230350826479396169919496331694912269236021589305104914065692024633605545682960485382658317083519439896223914809671958985614449832968502804394284603806498146722780214587537106183457508118506602826906261033493847031630860957654002225445358956847149371205119794332012547181752753507797022931980908100462509326502439102491331083803872407235779763459004153616216304938291636105644293055444980571851833996349467322110986122607043162502018966557209205283821430521221237568760340212729112434894292629275100415364773527243506794236142738628134241662343048514112988689529593500079916365899992838147306759026088956199604708293033934595339433123750179258276298635153082164442870255978483784100591427731579935496061581020425943479639687684019442076595170412574155853965089514041714150376659768398377923028408729107012981031844211804345863393456200657869442594692403179541682898815815441910752584698517206930563466601599240603233832740

1341 decimal digits or 4452 bits.

Alois