MathGroup Archive 2014

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Goodstein expansion

  • To: mathgroup at smc.vnet.net
  • Subject: [mg132327] Re: Goodstein expansion
  • From: Murray Eisenberg <murray at math.umass.edu>
  • Date: Mon, 10 Feb 2014 03:00:47 -0500 (EST)
  • Delivered-to: l-mathgroup@mail-archive0.wolfram.com
  • Delivered-to: l-mathgroup@wolfram.com
  • Delivered-to: mathgroup-outx@smc.vnet.net
  • Delivered-to: mathgroup-newsendx@smc.vnet.net
  • References: <20140208090230.178B569E8@smc.vnet.net> <20140209094847.0694269F1@smc.vnet.net>

A correction to my reply: in (2), I should have used q (for "quotient") rather than d (as in "divisor").

Also, in (1), find the greatest nonnegative integer k such that b^k <= n.

On Feb 9, 2014, at 4:48 AM, Murray Eisenberg <murray at math.umass.edu> wrote:

> It's unclear whether the question is simply to find the base-b expansion of an integer or, instead, to write an algorithm to do it.
>
> If the former, several built-in Mathematica functions do this (did you bother to search the documentation for "base" to discover them yourself??):
>
>      BaseForm[87, 5]
>   (* 322   *)
>   (*    5  *)
>      Head[BaseForm[87, 5]]
>   (* BaseForm *)
>
> Note that for BaseForm, the base b must be in Range[2, 36] -- so as to allow use of the ten digits together with the twenty-six letters of the English alphabet for the coefficients.
>
>      IntegerDigits[87, 5]
>   (* {3, 2, 2} *)
>
> Note no upper bound, other than system limits, on the size of the base with IntegerDigits. And probably the output from IntegerDigits is more useful for further calculation than that of BaseForm.
>
>      IntegerString[87, 5]
>   (* 322 *)
>      Head[IntegerString[87, 5]]
>   (* String *)
>
> If, however, your question is to write code implementing an algorithm to do it, then a good way to start would be to look at a proof of what I like to call the "Base Value Theorem", which asserts that for arbitrary integer base b > 1 and arbitrary positive integer n, there exists a unique nonnegative integer k and a unique list c[[0]], c[[1]], . . ., c[[k]] such that:
>
>    n == Sum[c[[j]] b^j, {j, 0, k}]
>
> The essence of the proof is the following, for a given b and n:
>
> (1) Find the smallest positive integer t such that b^t > n. Set k = t - 1.
>
> (2) Divide n by b^k, getting divisor d and remainder r. Set c[[k]] = d.
>
> (3) Repeated apply the preceding steps but with r in place of the original n.
>
> To implement this in Mathematica, you'd probably want to use recursion. For Step (2), of course use Quotient and Mod.
> The trick is undoubtedly how to do Step (1). If you're willing to use logarithms, then there's an obvious way to proceed. But if you want to keep strictly within the domain of integers, then you'd want to form _some_ power of b that's greater than n and then step down from it to obtain t; an extravagant way would be to start with the (possibly too-huge) power b^n.
>
> Hope this helps.
>
> On Feb 8, 2014, at 4:02 AM, Brambilla Roberto Luigi (RSE) <Roberto.Brambilla at rse-web.it> wrote:
>
>>
>> The Goodstein expansion of integers  (see for instance  Stillwell," Roads to Infinity", pag.47)
>>
>> Given an integer n we can write it as sum of powers of  2
>>
>> 87=2^6+2^4+2^2+1=2^(2^2+2)+2^(2^2)+2^2+2^0
>>
>> More generally assuming an integer b as a base, we can write  n as a sum of power of b with coefficients <b
>> es.:  b=5
>>
>> 87=3*5^2+2*5^1+2*5^0.
>>
>> I can do it by means of a long and obvious routine with lots  of  If[] and While[].
>> May be someone can do it by means of the recursive properties of Mathematica language?
>> Many thanks to all the friends of this group!
>> Roberto
>>
>>
>>
>>
>>
>> RSE SpA ha adottato il Modello Organizzativo ai sensi del D.Lgs.231/2001, in > forza del quale l'assunzione di obbligazioni da parte della Societ avvieune con firma di un procuratore, munito di idonei poteri.
>> RSE adopts a Compliance Programme under the Italian Law (D.Lgs.231/2001). Ac> cording to this RSE Compliance Programme, any commitment of RSE is taken by the signature of one Representative granted by a proper Power of Attorney. Le informazioni contenute in questo messaggio di posta elettronica =
> sono ris=
>> ervate e confidenziali e ne e' vietata la diffusione in qualsiasi =
modo =
> o for=
>> ma. Qualora Lei non fosse la persona destinataria del presente =
> messaggio, La=
>> invitiamo a non diffonderlo e ad eliminarlo, dandone gentilmente =
> comunicazi=
>> one al mittente. The information included in this e-mail and any =
> attachments=
>> are confidential and may also be privileged. If you are not the =
> correct rec=
>> ipient, you are kindly requested to notify the sender immediately, to =
=
> cancel=
>> it and not to disclose the contents to any other person.
>>
>>
>
> Murray Eisenberg                                murray at math.umass.edu
> Mathematics & Statistics Dept.     
> Lederle Graduate Research Tower      phone 240 246-7240 (H)
> University of Massachusetts              
> 710 North Pleasant Street               
> Amherst, MA 01003-9305

=97=97
Murray Eisenberg                                murray at math.umass.edu
Mathematics & Statistics Dept.      
Lederle Graduate Research Tower      phone 240 246-7240 (H)
University of Massachusetts               
710 North Pleasant Street                
Amherst, MA 01003-9305









  • Prev by Date: Re: Memory leaks problem
  • Next by Date: hold question
  • Previous by thread: Re: Goodstein expansion
  • Next by thread: Re: Goodstein expansion