[OT] Reciprocal function?

[Terry Reedy]

"Anton Vredegoor" <anton at vredegoor.doge.nl> wrote in message
news:aril5k$e07$1 at news.hccnet.nl...
> def rowinc(x,base):
>     i,j = 0,1
>     while i <= x:
>         j = j * base
>         i = i + j
>     return j

Odd and misleading name.  Somewhat odd function.  For x < 0 (which
your problem specification may exclude), rowinc==1.  Otherwise, it
return the largest power of base, base**n, such that sum(k=1..n-1;
base**k)  <= x.  For x>=0, this is at least base**1.

When base=2 and hence base-1==1, this is the largest power of 2 in
x+2.  Which is to say, n is the index of the high order 1-bit in the
binary expression of x+2.  This could be done more simply with shifts,
but this does not generalize very well to other bases.

> def concat(a,b,base):
>     f = rowinc(b,base)
>     return f*(a+1)+b

This multiply-add (which characterization is the key to your problem)
has nothing obvious to do with concat-enation.  You implicitly assume
below that a and b are counts (non-negative ints).  It would be less
confusing if you did not add 1 to a, so a is the actual multiplier
rather than 1 less, and instead required input to be positive rather
than just non-negative.

> And, for the moment, lets assume "base" is fixed to the value 2.
>
> Then concat(9,5,2) will return 45.
> But concat(3,13,2) will also return 45.
>
> In fact if the number that concat returns is known, and the "base"
> argument is also known, the function below can be used to calculate
> how many other tuples (a,b) will have the same result:
>
> def seqlen(x,base):
>     i,j,k = 0,1,0
>     while i <= x:
>         j = j * base
>         i = i + j
>         k = k + 1
>     return k

This version of rowinc returns n instead of base**n.

> So seqlen(45,2) returns 5. The number of possible tuples (a,b) that
> make concat(a,b,2) return 45 is seqlen(45,2)-1 which is 4.

Only because you exclude concat(-1,45,2) = 45.

> For (a,b) in [(0, 29), (3, 13), (9, 5), (21, 1)], concat(a,b,2)
> returns 45 and there are no other tuples (a,b) that return 45 for
> concat(a,b,2).

Only with the unstated condition.

>
> Now I need a function that looks a bit like this:
>
> def splitat(i,a,base):
> """
> returns the i'th tuple (x,y) out of the set of possible
> tuples that make concat(x,y,base) return a
> """
>     return x,y
>
> Any pointers appreciated.

Overloading a as both a param of concat and its result is poor.  I
will call the result cc instead.  Defining i'th tuple depends on the
ordering.   Sorting on b instead of a makes problem slightly easier.
In any case, the 'inverse' of multiply-add is divmod(), possibly
adjusted.  Because of the rowinc condition linking b, base, and power
of base, there is (definitely for base 2 and perhaps for others - not
sure) one possible value of a,b for each possible value of rowinc,
each of which is a positive power of base.  So generate the list of
tuples by looping thru powers of base.  Example for cc=45 and base=2
to generate pairs (a+1,b) (I'll let you do subtraction of 1 from a+1):

divmod(45,2) = (22,1) #OK since rowinc(1,2)=2
divmod(45,4) = (10,5) # OK since rowinc(5,2) = 4
divmode(45,8) = (5,5) # not OK
# adjust a down and b up to maintain product-sum of 45
  adjust to 4,13(=5+8) # OK since rowinc(13,2)=8
divmod(45,16) = (2,13) # not OK
  adjust to 1,29(=13+16) #OK since rowinc(29,2)=16
divmod(45,32) = (1,13) # not OK
  adjust to 0.45 #stop because a+1<1 not allowed
return list of 4 tuples

With other bases, you might have to adjust more than once.  If doing a
lot of calculations with one base, it would be worthwhile to calculate
a vector of rowinc results.

Terry J. Reedy