Ruud H.G. van Tol on Wed, 29 Dec 2021 14:55:51 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: factor(x+1)



On 2021-12-29 14:38, Bill Allombert wrote:
On Wed, Dec 29, 2021 at 02:12:14PM +0100, Ruud H.G. van Tol wrote:

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

Thanks, that really helps!

I forgot to mention
that I'd like to stop at some minimal factor,
being 3 in my example. (so no 3 -> 2^2-1 step)

Am now considering using basically your approach,
with each element a factor-Vec.

With only 2 and 3 around,
I could also use 2 elements per step,
but "flattening" always bites some day.

-- Ruud