login
Form a permutation of the positive integers, p_1, p_2, ..., such that the average of each initial segment is an integer, using the greedy algorithm to define p_n; sequence gives p_1 + ... + p_n.
3

%I #34 Aug 15 2023 08:14:28

%S 1,4,6,12,20,24,35,40,54,70,77,96,117,126,150,160,187,216,228,260,273,

%T 308,345,360,400,442,459,504,522,570,620,640,693,748,770,828,851,912,

%U 975,1000,1066,1092,1161,1232,1260,1334,1410,1440,1519,1550

%N Form a permutation of the positive integers, p_1, p_2, ..., such that the average of each initial segment is an integer, using the greedy algorithm to define p_n; sequence gives p_1 + ... + p_n.

%C It appears that a(n) is divisible by n. - _Michael Somos_, Jan 29 2004

%C Somos's conjecture is proved in both Shapovalov (1996) and Venkatachala (2009). - _Jeffrey Shallit_, Jul 18 2023

%H Alois P. Heinz, <a href="/A019445/b019445.txt">Table of n, a(n) for n = 1..10000</a>

%H J. 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 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 The Math Forum, <a href="http://mathforum.org/wagon/fall96/p818.html">Problem of the Week 818</a>.

%H 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.

%F Partial sums of A019444. - _Sean A. Irvine_, Mar 17 2019

%F a(n) = n * A019446(n). - _Joerg Arndt_, Jul 23 2023

%Y Cf. A019444, A019446.

%K nonn

%O 1,2

%A _R. K. Guy_, Tom Halverson (halverson(AT)macalester.edu)