Re: factor(x+1)

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Wed, Dec 29, 2021 at 02:12:14PM +0100, Ruud H.G. van Tol wrote:
> 
> I think I am looking for a decent data-structure
> to store a factor(x+1) tree.
> But if you see a different angle on it, don't hesitate.
> 
> I'm considering Vec-of-Vec, to mean something like (vecprod(v)-1).
> 
> Example:
> 103
> -> 2^3*13
> -> 2^3*(2*7-1)
> -> 2^3*(2*(2^3-1)-1)

It seems to me you should only keep the exponents and work backward:
Try this:

tofp1(x)=my(v=valuation(x,2));x>>=v;if(x==1,return([v]),concat(v,tofp1(x+1)))
fromfp1(v)=my(n=1);v=Vecrev(v);for(i=1,#v,n=2^v[i]*n-1);n+1

? tofp1(103)
%18 = [0,3,1,3]
? 2^0*(2^3*(2^1*(2^3-1)-1)-1)
%20 = 103
? fromfp1([0,3,1,3])
%21 = 103

Cheers,
Bill.