Re: Neujahrsaufgabe: Basisverschiebung in Zahlendarstellungen

["Udo und Susanne Krause" <su.krause@XXXXXXX.ch>]

Liebe Freundinnen und Freunde von Zahlendarstellungen,

> man fertige eine Funktion und ihre notwendigen Hilfsfunktionen, um in  
> einer Darstellung der natürlichen Zahl x zur Basis b > 1 alle b durch b  
> + 1 zu ersetzen.

Okay, die Basisdarstellung wird durch

baseS[b_Integer /; b > 1, n_Integer?Positive] := If[n < b,
  {b, SparseArray[{1} -> n]},
  {b, SparseArray[
    o_ /; Mod[Floor[n b^(1 - o)], b] > 0 ->
     Mod[Floor[n b^(1 - o)], b], {Floor[Log[b, n]] + 1}]}
  ]

hergestellt, die Rückwandlung in die Dezimalbasis ist durch

deciS[{b_Integer, l_SparseArray}] :=
 Block[{aR = Most[ArrayRules[l]]},
  Plus @@ Times[aR /. Rule[{__}, y_] :> y,
    b^(aR /. Rule[{x_}, __] :> x - 1)]
  ]

gegeben. Die gesuchte Funktion ist rekursiv:

hase[{b_Integer, l_SparseArray}] :=
 {b + 1, SparseArray[
   ArrayRules[l] /.
    Rule[{x_Integer /; x > b}, y_] :>
     Rule[{deciS[hase[baseS[b, x - 1]]] + 1}, y]
   ]
  }

Wozu braucht man soetwas? Mit der Subtraktion von 1 in
der Basisdarstellung

m1[{n_Integer, {b_Integer, l_SparseArray}}] :=
 Block[{inL = ArrayRules[l], r},
  r = Cases[inL, Rule[{n}, y_] -> y];
  If[Length[r] == 0,
   {n + 1, {b, SparseArray[Prepend[inL, Rule[{n}, b - 1]]]}}, (* else *)
   inL = Delete[inL, Position[inL, Rule[{n}, _]]];
   If[First[r] > 1,
    {n, {b, SparseArray[Prepend[inL, Rule[{n}, First[r] - 1]]]}}, (* else  
*)
    If[Length[inL] > 1,
     {n, {b, SparseArray[inL]}}, (* else *)
     {n, {b, l}} (* identity *)
     ]
    ]
   ]
  ]

igelTest[l1_List, l2_List] := First[l2] > First[l1]
igel[l_List] := Last[NestWhile[m1, {1, l}, igelTest, 2]]

kann man "Hase und Igel bei den Ordinalzahlen" darstellen:

connesHI[b_Integer, n_Integer?Positive, s_Integer?Positive] :=
 NestList[igel[hase[#]]&, baseS[b, n], s] /; b > 1

und die sind folgendermassen
(http://www.alainconnes.org/docs/Inteng.pdf) beschrieben:

You take a number N, not too big, they had taken 5 or
something like that. They had learnt to write numbers
in various bases, 2, 3, etc. I explained
to them that one writes the number in base 2, then the
hare comes and replaces all the 2's
by 3's; thus 5 = 2^2 + 1 gets replaced by 3^3 + 1 = 28 ...
and the tortoise just subtracts 1; then
one writes the result in base 3, and the hare comes and
replaces all the 3' s by 4' s; and the
tortoise subtracts 1 again, etc. Well, the extraordinary
phenomenon which comes from the theory of ordinals, is
that the tortoise wins:  after a finite number of steps
and even though you have the impression that the hare
makes absolutely gigantic jumps each time, you get 0!
And what's hard to believe, it is that this cannot
be proved in the framework of Peano arithmetic.
The proof uses the theory of ordinals!

Kann jemand anhand der Implementation sehen, warum der Igel gewinnt?

Mit den besten Grüssen
Udo.

P.S.: Mma hat bei SparseArrays einen maximalen Index von 2^31 - 1,
das wird vom o.g. Code nicht abgefangen.

--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/