A125033

User login

Collaborative Books

Syndicate

What is this?

Posted on 2006-11-19 18:13 By alec ( Maple Rating 4

1470)

Categories:

Sequence A125033 in the OEIS submitted by Paul D. Hanna and Richard J. Mathar, is defined as

Number of labeled nodes in generation n of a rooted tree where a node with label k has k child nodes with distinct labels, such that each child node is assigned the least unused label in the path that leads back to the root node with label '1'.

The example given there shows how to obtain first 5 elements:

Labels for the initial nodes of the tree for generations 0..4:
gen 0: [1];
gen 1: (1)->[2];
gen 2: (2)->[3,4];
gen 3: (3)->[4,5,6], (4)->[3,5,6,7];
gen 4: (4)->[5,6,7,8], (5)->[4,6,7,8,9], (6)->[4,5,7,8,9,10],
(3)->[5,6,7], (5)->[3,6,7,8,9], (6)->[3,5,7,8,9,10], (7)->[3,5,6,8,9,10,11];

I used the following back-tracking procedure to calculate it,

f:=proc(n::integer[4],A::Array(datatype=integer[4]),
B::Array(datatype=integer[4]))::integer[4]; local c::integer[4],
i::integer[4],len::integer[4],m::integer[4]; c,len,m:=0,3,3;
while len>1 do if len=n then c:=c+1;m:=A[len];B[m]:=0;len:=len-1;
B[A[len]]:=B[A[len]]+1 elif B[A[len]]<=A[len] then for i from m+1
do if B[i]=0 then break fi od; len:=len+1;A[len]:=i;B[i]:=1;m:=2
else m:=A[len];B[m]:=0;len:=len-1;B[A[len]]:=B[A[len]]+1 fi od; c end:

cf:=Compiler:-Compile(f):

F:=proc(n::posint) local A,B;
if n<3 then 1 elif n=3 then 2 else
A:=Array([$1..3,0$(n-3)],datatype=integer[4]);
B:=Array([1$3,0$((n-2)*(n+1)/2)],datatype=integer[4]);
cf(n,A,B) fi end:

seq(F(n),n=1..12);

  1, 1, 2, 7, 36, 248, 2157, 22761, 283220, 4068411, 66367834,

        1213504295

That confirms Richard Mathar's and Paul Hanna's calculations and gives one more element of the sequence. Further elements could not be calculated on my 32-bit computer using this procedure, because they are greater than 2^32. Changing the types of c and f from integer[4] to float[8] allows further calculations. I did that and after about an hour got the next element,

F(13);
                      24606397802

Alec Mihailovs
http://mihailovs.com/Alec/

alec's blog
Login or register to post comments

Comments

why not datatype long?

Comment on 2006-11-22 15:03 from Axel Vogt ( Maple Rating 4

948)

I was not aware that integer[8] is not supported here ...

But your time for F(13) is not really encouraging to try
for F(14) :-)

Is there a special reason for looking at that sequence?

Long integers

Comment on 2006-11-22 15:58 from alec ( Maple Rating 4

1470)

I didn't read the Compiler help files recently, but as far as I recall, integer[4] is the largest available format for integer and float[8] - for float.

Even if integer[8] was supported, that wouldn't help in this situation, because x86 registers are 32 bit - they can't fit longer numbers, so longer integers would have to be transfered to FPU anyway, the same as float[8] (and the FPU is about 3 times slower than x86). Actually, only c needed to be transfered there - and there is only one operation with it during a loop, so that doesn't slow down much the whole process.

Certainly, in the form it is written, it is not a big problem to rewrite it directly in assembler - that would give at least 3 times speed increase comparing to C (usually it is much more, but for such simple things as adding or subtracting 1s C compilers can't do much worse than making it about 3 times slower than assembler, I think). With optimization, I might get to 10-20 times speed increase - that would allow to get F(14) in a reasonable time - but optimization in assembler requires a lot of hard work, and I am not that interested in that to do it...

All sequences in the OEIS are interesting. There was a discussion about this particular sequence on the seqfan mailing list.

__________
Alec Mihailovs
http://mihailovs.com/Alec/