# 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]]; 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. 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. Jan 3 at 19:27
• @Emanuel I see. Thank you for the clarification. Jan 3 at 19:28
• Sorry, but I get an recursion error. MMA version12.1 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 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... Jan 3 at 17:52