8
$\begingroup$

I would like to perform an operation over IntegerDigits recurrently.

The operation is the sum of cubes of the digits, for example:

$12 \rightarrow (1^3 + 2^3) = 9$.

Outside of the RecurrenceTable all looks fine:

f[k_] := Total[IntegerDigits[k]^3]
f[12]
(* out: 9 *)

But inserted inside the RecurrenceTable, the output is not what I expect:

RecurrenceTable[{a[n+1] == Total[IntegerDigits[a[n]]^3], a[1] == 12}, a, {n, 1, 3}] 
(* out: {12,{4,5},{{7},{8}}} *)

Why does it behave this way and what is the right way to do such task?

$\endgroup$
  • $\begingroup$ Welcome! To make the most of Mma.SE start by taking the tour now. It will help us to help you if you write an excellent question. Edit if improvable, show due diligence, give brief context, include minimal working example of code and data in formatted form. As you receive give back, vote and answer questions, keep the site useful, be kind, correct mistakes and share what you have learned. $\endgroup$ – rhermans May 30 '18 at 18:30
  • $\begingroup$ What's the expected output for n=3? a[1]=12, then a[2]=f[a[1]]=f[12]=9, and then a[3]=f[a[2]]=f[9]=9^3=729? And next would be a[4]=f[a[3]]=f[729]=1080? Then the straightforward way would be NestList[f, 12, 3] yielding {12, 9, 729, 1080} $\endgroup$ – corey979 May 30 '18 at 18:44
  • $\begingroup$ Inspired by this thread, I posted a question about it on math.SE $\endgroup$ – corey979 May 31 '18 at 5:59
  • $\begingroup$ @corey979, The actual origin of the task is from here $\endgroup$ – Kiryaka May 31 '18 at 8:38
7
$\begingroup$

First, as I noted in the comment, a much simpler approach is to use NestList:

NestList[f, 12, 3]

{12, 9, 729, 1080}


Let's explain what happens when RecurrenceTable is employed.

First, let's see how the code is run:

RecurrenceTable[{a[n + 1] == Total[IntegerDigits[a[n]]^3], 
   a[1] == 12}, a, {n, 1, 3}] // Trace

enter image description here

This yields a suspicious term a[1+n] == 3 + IntegerDigits[a[n]]. So, let's see a FullForm:

Total[IntegerDigits[a[n]]^3] // FullForm

3 + IntegerDigits[a[n]]

Something's wrong with Total! Or is it? From the docs: "Total[list] is equivalent to Apply[Plus, list]". So, because the FullForm of IntegerDigits[a]^3 is Power[IntegerDigits[a], 3], one gets from Apply[Plus, Power[IntegerDigits[a], 3] the incorrect expression 3 + IntegerDigits[a]. So one cannot use Total like this.

So maybe Sum will be a solution?

Sum[(IntegerDigits[a[n]]^3)[[i]], {i, 1, Length@(IntegerDigits[a[n]]^3)}]

3 + IntegerDigits[a[n]]

Not good; it gives the same result as Total. Some weird ideas like #^3 & /@ IntegerDigits[a[n]] are also no good.

Let's define then

g[k_Integer] := Block[{seq}, seq = IntegerDigits[k]; 
  Sum[seq[[i]]^3, {i, 1, Length@seq}]]

Then, g[a[n]] gives g[a[n]] - this is good, because if we skip the Integer part from the definition, we'll get a[n]^3 instead, leading to new problems (to see what's going on under the hood in such a case, run RecurrenceTable[{a[n + 1] == g[a[n]], a[1] == 12}, a, {n, 1, 2}] // Trace).

So, eventually, with the above (proper) definition of g one gets:

RecurrenceTable[{a[n + 1] == g[a[n]], a[1] == 12}, a, {n, 1, 4}]

{12, 9, 729, 1080}

But still... If there's such a difference between defining g[k_] and g[k_Integer], then maybe let's come back to the very beginning and define f as

Clear[f]
f[k_Integer] := Total[IntegerDigits[k]^3]

Then

RecurrenceTable[{a[n + 1] == f[a[n]], a[1] == 12}, a, {n, 1, 4}]

{12, 9, 729, 1080}

yields the correct answer!

So the whole convoluted line of reasoning lead to simply adding Integer to the initial definition. Comparing the FullForms of the two versions, one sees that in the Integer case the function is not evaluated at all unless it gets an argument with the specified Head - in this case, Integer, i.e. a definite number on which all the arithmetics can be performed without the unexpected behaviour of Total. So, in the end, this makes perfect sense.


Mathematical questions that arise

What happens with the sequence for large n? Let's simultaneously investigate this with the dependence on the initial condition a[1]==a1:

ListPlot[RecurrenceTable[{a[n + 1] == f[a[n]], a[1] == #}, 
     a, {n, 1, 100}], PlotLabel -> #, PlotRange -> All, 
    Frame -> True] & /@ Range[100] // FlipView

Checking the above plots, one'll notice that the sequences converge to either 1, 2, or 3 interchanging values, e.g.

enter image description here

Is it universal? Let's compute the sequences (of length 100) for $a_1\in [1,10^4]$, take the last 20 iterations, DeleteDuplicates and calculate the Length:

(per = Length /@ 
    DeleteDuplicates /@ (RecurrenceTable[{a[n + 1] == f[a[n]], 
          a[1] == #}, a, {n, 80, 100}] & /@ Range[10000])) // 
 ListPlot[#, Frame -> True, PlotRange -> All] &

enter image description here

Indeed, only three values occur, with the frequencies

Tally[per]

{{1, 8543}, {3, 956}, {2, 501}}

I haven't noticed any obvious pattern in the a1s that lead to different multiplicities of the limitting sequence. Questions that arise:

  1. Are the numbers $1,2,3$ the only multiplicities possible for all $a_1\in\mathbb{N}$?
  2. What governs the value of the multiplicity in dependence on $a_1$?
  3. How universal this behaviour is when sums of squares, quartics, etc. are considered?
  4. Do other types of functions of the IntegerDigits have such interesting/universal properties?
  5. What are other interesting questions to ask about?
$\endgroup$
  • $\begingroup$ We seem to have arrived at very similar conclusions :-) $\endgroup$ – MarcoB May 30 '18 at 19:47
  • $\begingroup$ @MarcoB Hm, you posted your answer while I was writting up my and didn't see it before I posted; sorry. However, mine is a bit more in-depth about how to arrive to such conclusions, and I provide a different workaround than you, so let me leave my answer as it is. $\endgroup$ – corey979 May 30 '18 at 19:51
  • $\begingroup$ Oh yes, that's fine! I didn't mean to suggest that you had to change anything. In fact, I upvoted your answer. $\endgroup$ – MarcoB May 30 '18 at 19:53
  • $\begingroup$ @MarcoB Same; inactivating Total is a neat trick. Although, I've just found the ultimate solution - see my edit :) $\endgroup$ – corey979 May 30 '18 at 20:02
  • $\begingroup$ @corey979, Thank you for such a detailed deep dive. That gives me insights on how to investigate things by myself. One question tho, what was your intuition behind trying to fix the type in the function definition f[k_Integer] ? I do not see how your previous steps leads to this idea. $\endgroup$ – Kiryaka May 31 '18 at 5:28
6
$\begingroup$

The problem is that in your equation within RecurrenceTable the expression

Total[IntegerDigits[a[n]]^3]

"prematurely" evaluates to :

3 + IntegerDigits[a[n]]

In a simpler case, you can see this more clearly:

Clear[x]
Total[x^3] (* which is the same as Total[Power[x, 3]] *)
(*Out:  x + 3*)

Indeed, this may be surprising, but it is behavior described in the documentation. In fact,

Total[list] is equivalent to Apply[Plus, list]

Total[f[e1, e2, ...]] gives the sum of the $e_i$ for any head $f$.


You can define the transformation as a separate function, or you can brute-force your way around it by temporarily inactivating Total, then reactivating it at the end of the calculation:

RecurrenceTable[
  {a[n + 1] == Inactive[Total][IntegerDigits[a[n]]^3], a[1] == 12}, a, {n, 1, 9}
] // Activate

(* Out: {12, 9, 729, 1080, 513, 153, 153, 153, 153} *)
$\endgroup$
4
$\begingroup$

An alternative solution is NestList

ClearAll[f];
f[k_Integer] := Total[IntegerDigits[k]^3]
NestList[f, 12, 7]
{12, 9, 729, 1080, 513, 153, 153, 153}

or

ClearAll[f];
f[k_Integer] := Sum[i^3, {i, IntegerDigits[k]}]

Other answers already gave a better explanation on the behaviour of you observed in RecurrenceTable been a consequence of the definition of Total as Apply[Plus,list], implying that the Head of the expression is replaced by Plus. As noted in the comments I mistakenly used Integers instead of Integer in my attempts of solution.

$\endgroup$
  • $\begingroup$ Why did you use type case in your functions? I'm asking because the way you define the function - it will also works perfectly fine inside the RecurrenceTable (see corey979 investigation). So what was you intuition behind restricting the type? Is it just that you always try to be as type strict as possible for the task, or is it something about this exactly this task that require it? $\endgroup$ – Kiryaka May 31 '18 at 5:47
  • 1
    $\begingroup$ @Kiryaka Mostly as a habit, it's good practice to constrain the definition to the argument you are expecting to have. In this case I also though RecurrenceTable was trying to be clever and do some analytical test on the function. As presumably IntegerDigits would not act as a well behaved algebraic definition, I thought was best to avoide any other evaluation other than with an Integer. $\endgroup$ – rhermans May 31 '18 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.