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,2

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

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

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

The Math Forum, Problem of the Week 818

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

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

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

Prog

(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]||(#A<A[n]=n+c++)|| A[n+c]=n); A} \\ M. F. Hasler, Nov 27 2019

Crossrefs

Cf. A019445, A019446, A243700, A001622.

Sequence in context: A160855 A120232 A292961 * A195412 A069773 A122321

Adjacent sequences: A019441 A019442 A019443 * A019445 A019446 A019447

Keyword

nonn,nice

Author

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

Status

approved