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

É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

Math Forum, Problem of the Week 818

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

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