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.

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, 17, 45, 18, 48, 50, 20, 53, 55, 22, 58, 23, 61, 63, 25, 66, 26, 69, 71, 28, 74, 76, 30, 79, 31, 82, 84, 33, 87, 34, 90, 92, 36, 95, 97, 38, 100, 39, 103, 105, 41, 108, 110, 43, 113

Offset: 1

Author

R. K. Guy and Tom Halverson (halverson(AT)macalester.edu)

Keywords

• nonn
• nice

Comments

Self-inverse when considered as a permutation or function, i.e., a(a(n)) = n. - Howard A. Landman, Sep 25 2001

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

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

Comments from N. J. A. Sloane, Mar 29 2025 (Start):

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.

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).

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.

For other sequences derived from the present one, see A382162, A382168, and A382169.

(End)

References

• Muharem Avdispahić and Faruk Zejnulahi, An integer sequence with a divisibility property, Fibonacci Quarterly, Vol. 58:4 (2020), 321-333.

Links

• Franklin T. Adams-Watters, Table of n, a(n) for n = 1..10000
• Éric Angelini, Franklin Adams-Watters, Max Alekseyev, A. E. Povolotsky, N. J. A. Sloane, and R. G. Wilson v, a(n) divides the sum of the first a(n) terms of T, Various postings to the old Sequence Fans Mailing List, assembled by _N. J. A. Sloane_, Dec 24 2024
• Jon Asier Bárcena-Petisco, Luis Martínez, María Merino, Juan Manuel Montoya, and Antonio Vera-López, Fibonacci-like partitions and their associated piecewise-defined permutations, arXiv:2503.19696 [math.CO], 2025. See p. 18.
• Math Forum, Problem of the Week 818
• Jeffrey Shallit, Proving properties of some greedily-defined integer recurrences via automata theory, arXiv:2308.06544 [cs.DM], August 12 2023.
• A. Shapovalov, Problem M1517 (in Russian), Kvant 5 (1995), 20-21. English translation appeared in Quantum problem M185, Sept/October 1996 (beware, file is 75Mb).
• B. J. Venkatachala, A curious bijection on natural numbers, JIS 12 (2009) 09.8.1.
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A019445, A019446, A243700, A001622, A060143, A060144, A270788.

See also A382162, A382168, and A382169.

Programs

Mathematica

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]
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 *)
Fold[Append[#1, #2 Ceiling[#2/GoldenRatio] - Total[#1]] &, {1}, Range[2, 70]] (* Birkas Gyorgy, May 25 2012 *)

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

PARI

A019444_upto(N, c=0, A=Vec(1, N))={for(n=2, N, A[n]||(#AM. F. Hasler, Nov 27 2019

Formula

a(n) = A002251(n-1) + 1. (Corrected by M. F. Hasler, Sep 17 2014)

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

Lim_{n->infinity} max(n,a(n))/min(n,a(n)) = phi = A001622. - Stanislav Sykora, Jun 12 2017