cp's OEIS Frontend

A019444 a_1, a_2, ..., is a permutation of the positive integers such that the average of each initial segment is an integer, using the greedy algorithm to define a_n.

%I A019444 #102 Mar 31 2025 22:48:39
%S A019444 1,3,2,6,8,4,11,5,14,16,7,19,21,9,24,10,27,29,12,32,13,35,37,15,40,42,
%T A019444 17,45,18,48,50,20,53,55,22,58,23,61,63,25,66,26,69,71,28,74,76,30,79,
%U A019444 31,82,84,33,87,34,90,92,36,95,97,38,100,39,103,105,41,108,110,43,113
%N A019444 a_1, a_2, ..., is a permutation of the positive integers such that the average of each initial segment is an integer, using the greedy algorithm to define a_n.
%C A019444 Self-inverse when considered as a permutation or function, i.e., a(a(n)) = n. - _Howard A. Landman_, Sep 25 2001
%C A019444 That each initial segment has an integer average is trivially equivalent to the sum of the first n elements always being divisible by n. - _Franklin T. Adams-Watters_, Jul 07 2014
%C A019444 Also, a lexicographically minimal sequence of distinct positive integers such that all values of a(n)-n are also distinct. - _Ivan Neretin_, Apr 18 2015
%C A019444 Comments from _N. J. A. Sloane_, Mar 29 2025 (Start):
%C A019444 Let d(n) = number of 1 <= i <= n such that a(i) < i. The d(i) sequence begins 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, ..., and appears to be A060144 without its initial term.
%C A019444 Let r(n) = 1 if a(n) < a(n+1), otherwise 0, and let f(n) = 1 if a(n) > a(n+1), otherwise 0. Then R = partial sums of r(n) and F = partial sums of f(n) count the rises and falls, respectively, in the present sequence. It appears that R and F are essentially A060143 and A060144 (again).
%C A019444 If a(n) is the k-th term in a monotonically strictly increasing rum of terms, set R(n) = k. It appears that the sequence  R(n), n>=1, is essentially A270788.
%C A019444 For other sequences derived from the present one, see A382162, A382168, and A382169.
%C A019444 (End)
%D A019444 Muharem Avdispahić and Faruk Zejnulahi, An integer sequence with a divisibility property, Fibonacci Quarterly, Vol. 58:4 (2020), 321-333.
%H A019444 Franklin T. Adams-Watters, <a href="/A019444/b019444.txt">Table of n, a(n) for n = 1..10000</a>
%H A019444 Éric Angelini, Franklin Adams-Watters, Max Alekseyev, A. E. Povolotsky, N. J. A. Sloane, and R. G. Wilson v, <a href="/A243700/a243700_1.txt">a(n) divides the sum of the first a(n) terms of T</a>, Various postings to the old Sequence Fans Mailing List, assembled by _N. J. A. Sloane_, Dec 24 2024
%H A019444 Jon Asier Bárcena-Petisco, Luis Martínez, María Merino, Juan Manuel Montoya, and Antonio Vera-López, <a href="https://arxiv.org/abs/2503.19696">Fibonacci-like partitions and their associated piecewise-defined permutations</a>, arXiv:2503.19696 [math.CO], 2025. See p. 18.
%H A019444 Math Forum, <a href="http://mathforum.org/wagon/fall96/p818.html">Problem of the Week 818</a>
%H A019444 Jeffrey Shallit, <a href="https://arxiv.org/abs/2308.06544">Proving properties of some greedily-defined integer recurrences via automata theory</a>, arXiv:2308.06544 [cs.DM], August 12 2023.
%H A019444 A. Shapovalov, <a href="http://kvant.mccme.ru/1995/05/zadachnik_kvanta_matematika.htm">Problem M1517</a> (in Russian), Kvant 5 (1995), 20-21. English translation appeared in <a href="http://static.nsta.org/pdfs/QuantumV7N1.pdf">Quantum problem M185</a>, Sept/October 1996 (beware, file is 75Mb).
%H A019444 B. J. Venkatachala, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Venkatachala/venkatachala2.html">A curious bijection on natural numbers</a>, JIS 12 (2009) 09.8.1.
%H A019444 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A019444 a(n) = A002251(n-1) + 1. (Corrected by _M. F. Hasler_, Sep 17 2014)
%F A019444 Let s(n) = (1/n)*Sum_{k=1..n} a(k) = A019446(n). Then if s(n-1) does not occur in a(1),...,a(n-1), a(n) = s(n) = s(n-1); otherwise, a(n) = s(n-1) + n and s(n) = s(n-1) + 1. - _Franklin T. Adams-Watters_, May 20 2010
%F A019444 Lim_{n->infinity} max(n,a(n))/min(n,a(n)) = phi = A001622. - _Stanislav Sykora_, Jun 12 2017
%t A019444 a[1]=1; a[n_] := a[n]=Module[{s, v}, s=a/@Range[n-1]; For[v=Mod[ -Plus@@s, n], v<1||MemberQ[s, v], v+=n, Null]; v]
%t A019444 lst = {1}; f[s_List] := Block[{k = 1, len = 1 + Length@ lst, t = Plus @@ lst}, While[ MemberQ[s, k] || Mod[k + t, len] != 0, k++ ]; AppendTo[lst, k]]; Nest[f, lst, 69] (* _Robert G. Wilson v_, May 17 2010 *)
%t A019444 Fold[Append[#1, #2 Ceiling[#2/GoldenRatio] - Total[#1]] &, {1}, Range[2, 70]] (* _Birkas Gyorgy_, May 25 2012 *)
%o A019444 (PARI) al(n)=local(v,s,fnd);v=vector(n);v[1]=s=1;for(k=2,n,fnd=0;for(i=1,k-1,if(v[i]==s,fnd=1;break));v[k]=if(fnd,s+k,s);s+=fnd);v \\ _Franklin T. Adams-Watters_, May 20 2010
%o A019444 (PARI) A019444_upto(N, c=0, A=Vec(1, N))={for(n=2, N, A[n]||(#A<A[n]=n+c++)|| A[n+c]=n); A} \\ _M. F. Hasler_, Nov 27 2019
%Y A019444 Cf. A019445, A019446, A243700, A001622, A060143, A060144, A270788.
%Y A019444 See also A382162, A382168, and A382169.
%K A019444 nonn,nice
%O A019444 1,2
%A A019444 _R. K. Guy_ and Tom Halverson (halverson(AT)macalester.edu)