cp's OEIS Frontend

A373284 Number of permutations of {1, 2, 3, ..., n} that result in a final value of 0 by repeatedly iterating the process of "subtracting if the next item is greater or equal, otherwise adding" until there's only one number left.

%I A373284 #45 Mar 21 2025 09:37:57
%S A373284 0,0,1,1,3,10,52,459,1271,10094,63133,547565,4431517,42046100,
%T A373284 400782747,8711476734
%N A373284 Number of permutations of {1, 2, 3, ..., n} that result in a final value of 0 by repeatedly iterating the process of "subtracting if the next item is greater or equal, otherwise adding" until there's only one number left.
%C A373284 Let x_0 be a permutation on {1, 2, 3, ..., n}. Let x_k(i) be a function defined when 0 < i <= n - k that is constructed as follows:
%C A373284 If x_k(i + 1) >= x_k(i), then x_{k+1}(i) = x_k(i + 1) - x_k(i).
%C A373284 Otherwise, x_{k+1}(i) = x_k(i + 1) + x_k(i).
%C A373284 a(n) is the number of permutations x_0 that satisfy x_{n-1}(1) = 0.
%C A373284 From _Olivier Gérard_, Jun 04 2024: (Start)
%C A373284 The sequence of number of different values is:
%C A373284   1, 2, 4, 9, 32, 75, 179, 230, 933
%C A373284 The sequence of maxima of this process is A001792:
%C A373284   1, 3, 8, 20, 48, 112, 256, 576, 1280
%C A373284 Indeed, the maxima is attained only once and always for the last permutation in lexicographic order : n, n-1, n-2, ..., 1 (End).
%e A373284 For n=5, one of the a(5) = 3 solutions is (1, 4, 5, 2, 3), whose trajectory to 0 is
%e A373284   1 4 5 2 3
%e A373284    3 1 7 1
%e A373284     4 6 8
%e A373284      2 2
%e A373284       0
%t A373284 Block[{fn, cperm, rs}, fn = Function[ls, First @ NestWhile[ MapThread[If[#2 < #1, #1 + #2, #2 - #1] &, {Most@#, Rest@#}] &, ls, Length@# > 1 &]]; cperm = Function[n, Total[ ParallelMap[ Boole[fn@# == 0] &, Permutations @ Range @ n]]]; rs = Table[cperm @ n, {n, 10}]; rs] (* _Mikk Heidemaa_, Mar 14 2025. Based on the Python code below *)
%o A373284 (Python)
%o A373284 from itertools import permutations
%o A373284 def f(t):
%o A373284     if len(t) == 1: return t[0]
%o A373284     return f([t[i]+t[i+1] if t[i+1]<t[i] else t[i+1]-t[i] for i in range(len(t)-1)])
%o A373284 def a(n): return sum(1 for p in permutations(range(1, n+1)) if f(p) == 0)
%o A373284 print([a(n) for n in range(1, 10)]) # _Michael S. Branicky_, May 30 2024
%Y A373284 Cf. A001792, A131502.
%K A373284 nonn,nice,hard,more
%O A373284 1,5
%A A373284 _Bryle Morga_, May 30 2024
%E A373284 a(12)-a(13) from _Michael S. Branicky_, May 30 2024
%E A373284 a(14)-a(16) from _Bert Dobbelaere_, Jun 09 2024