# Using dynamic programming to compute an integer sequence

Let a[n] = n + 1 - a[EulerPhi[n]], n integer > 0. I have Python code that generates the sequence using dynamic programming. How can I achieve the same thing elegantly/idiomatically in Mathematica?

This is my Python code:

from sympy import totient as phi

N = 100

# a(n) = n + 1 - a(phi(n)), n > 0

a = [ 0 ] * N

# a(1) = 1 + 1 - a(phi(1)) = 2 - a(1) => 2 a(1) = 2 => a(1) = 1

a[1] = 1

# a(n), n > 1 computed using dynamic programming

for n in range(2, N):
a[n] = n + 1 - a[phi(n)]

print(a[1:])

• a[1] = 1; a[n_] := n + 1 - a[EulerPhi[n]]; Or to speed it up: a[n_] := a[n]= n + 1 - a[EulerPhi[n]]; – Daniel Huber Jan 3 at 16:09
• I think your obsession with a one-liner is counterproductive. For instance, if I had to read the version provided by Daniel Huber versus the version provided by kglr, I would find the recursive version much clearer. The one liner would qualify as obfuscated code in my opinion. – MarcoB Jan 3 at 18:49
• @MarcoB Well, I agree. In this case tho, we're literally talking about a column in a db. The people at OEIS actually reprimanded me for providing 100 terms of my integer sequence. 70 terms was acceptable. Code for generating sequences is just another column with similar byte size restrictions. This is why I asked for a 1-liner. – Emanuel Landeholm Jan 3 at 19:27
• @Emanuel I see. Thank you for the clarification. – MarcoB Jan 3 at 19:28
• Sorry, but I get an recursion error. MMA version12.1 – Daniel Huber Jan 4 at 17:17

This is a good chance to use #0:)

If[#1 == 1, 1, # + 1 - #0[EulerPhi @ #]] & /@ Range[20]

 {1, 2, 2, 3, 3, 5, 3, 6, 5, 8, 4, 10, 4, 10, 10, 11, 7, 14, 6, 15}


Make it Listable:

  Function[, If[#1 == 1, 1, # + 1 - #0[EulerPhi @ #]], Listable] @ Range[20]

{1, 2, 2, 3, 3, 5, 3, 6, 5, 8, 4, 10, 4, 10, 10, 11, 7, 14, 6, 15}

• Thanks! I've used # before but I've never quite managed to commit the syntax/semantics to long term memory. I write Matehematic snippets like once a year or so. Any chance you could rewrite that as a 1-liner? Would something like "Function[, If[#1 == 1, 1, # + 1 - #0[EulerPhi @ #]], Listable] @ Range[20]" work?For that OEIS clout. After all, OEIS db columns is all about bytes. Edit: Holy mother of g*d, it actually worked! :D – Emanuel Landeholm Jan 3 at 17:46
• @EmanuelLandeholm, please see the updated versions. – kglr Jan 3 at 17:49
• I'm accepting this as the answer. Thanks again! A340265, watch that space... – Emanuel Landeholm Jan 3 at 17:52