Smallest positive integer not yet appeared so that the sum of the first n elements is divisible by n

Given positive integer n, output a(n) where a is the sequence defined below:

a(n) is the smallest positive integer not yet appeared so that the sum of the first n elements in the sequence is divisible by n.

Example

• a(1) is 1 because it is the smallest positive integer that has not appeared in the sequence, and 1 is divisible by 1.
• a(10) is 16 because look at the first nine elements: 1,3,2,6,8,4,11,5,14. They sum up to 54, so for the first ten elements to sum up to a multiple of 10, a(10) would need to have a remainder of 6 when divided by 10. 6 has already appeared, so a(10) is 16 instead.

Testcases

n     a(n)
1     1
2     3
3     2
4     6
5     8
6     4
7     11
8     5
9     14
10    16
11    7
12    19
13    21
14    9
15    24
16    10
17    27
18    29
19    12
20    32
100   62
1000  1618
10000 16180


References

• What values of n and a(n) must we support? Aug 18, 2016 at 1:42
• @RohanJhunjhunwala Theoretically every positive number. Aug 18, 2016 at 1:44
• so bignum mandatory? Aug 18, 2016 at 1:47
• @RohanJhunjhunwala I said theoretically, meaning it is not mandatory. Aug 18, 2016 at 1:47
• Strangely related.
– xnor
Aug 18, 2016 at 4:07

Python 2, 43 bytes

r=.5+5**.5/2
lambda n:[n/r+1,n*r][n%r<1]//1


Outputs floats. Uses the relation

a(n) = A002251(n-1) + 1

to Wythoff pairs. Takes from the upper or lower Beatty sequence by multiplying or dividing by the golden ratio and converting to an integer.

• I think the precision is fine up to 2**32.
– xnor
Aug 18, 2016 at 4:27
• Then it does not work outside the boundary. Aug 18, 2016 at 4:28
• @LeakyNun I thought you said up to 2^31 -1 is ok?
– xnor
Aug 18, 2016 at 4:30
• What does it return for 2^31-1? Aug 18, 2016 at 4:34
• @LeakyNun It gives 6949403065.0.
– xnor
Aug 18, 2016 at 13:35

OCaml, 163 bytes

open List
let a x=let rec h m s=let rec n m s c=if fold_left(+)c(s)mod m<>0||mem c s then n m s(c+1)else c in if m=x then hd s else h(m+1)((n(m+1)s 2)::s) in h 1[1]


Online interpreter

Usage

>> open List
>> let a x=let rec h m s=let rec n m s c=if fold_left(+)c(s)mod m<>0||mem c s then n m s(c+1)else c in if m=x then hd s else h(m+1)((n(m+1)s 2)::s)in h 1[1];;
<< val a : int -> int = <fun>
>> a(100);;
<< int = 62


where >> is STDIN and << is STDOUT.

• Can you remove the whitespace after the last in? Aug 18, 2016 at 6:28
• I'm guessing you meant before? Thanks for editing in the demo! Aug 18, 2016 at 6:38
• Yes, I meant before Aug 18, 2016 at 6:39

Python 3, 102 bytes

Definitely not the shortest solution (not familiar with code golf) but I was bored so here it is in Python. I'm sure you could make it smaller with lambdas/filter.

def a(n,s=[]):
for j in range(1,n+1):
i=1
while i in s or(sum(s)+i)%j:i+=1
s+=[i]
return s[-1]

• Use a while loop for the second nested loop. Your solution currently does not theoretically support higher integers. Aug 18, 2016 at 2:38
• Rather than using 4 spaces, you can use a tab or one space. Aug 18, 2016 at 2:48
• You can also use space for the first level and then tab for the second level. Aug 18, 2016 at 2:48
• Make sure to include your byte count. Aug 18, 2016 at 2:48
• You ca put the opposite of the if condition as the while condition, and then append the item to the array outside the while loop. Aug 18, 2016 at 3:01

Pyth - 2321 18 bytes

Can probably streamline the generation process with more lambdas or other tricks, but this is my first answer in more than a month.

eem=+Yf!|}TY%+TsYh


Actually, 17 bytes

This uses xnor's algorithm. Golfing suggestions welcome. Try it online!

,;;φ(/u(φ*1φ(%<I≈


Here's a 31-byte version that uses the function definition, but with the oddity that, at first, the function returns the sequence a(n)-1, so the result needs to be incremented at the end. Try it online!

[]╗,1";#╜+;l@Σ%@╜í+uY"£╓╖n╜Nu


Ungolfing:

First algorithm

,;;                 Take the input, duplicate it twice
1φ(%<I    If input mod phi less than 1
(φ*          then input * phi
φ(/u             else input / phi + 1
≈   int() the result

Second algorithm

[]╗    Push a list to register 0 (call this res from now on)
,      Take input
1     Start function, push 1
"      Start string
;      Duplicate i
#╜+;   res + list(i), duplicate
l      len(new list)
@Σ     sum(new list)
%      sum % len
@╜í    Rotate i to top, check if i in res
+uY    (sum%len) + (i in res) + 1, negate (1 if i fits conditions, else 0)
"£     End string, turn into a function
╓      Push first (1) values where f(x) is truthy, starting with f(0)
╖     Append result to the list in register 0, end function
n      Run function (input) times
╜Nu    Return res[-1]+1


R, 99 bytes

f=function(n){a=n
b=c()
while(0<(a=a-1))b=c(f(a),b)
while(a<-a+1)if(!(sum(b)+a)%%n&!a%in%b)break
a}


Simple algorithm. Runs from n-1 to 1 and gathers all of those numbers in the sequence. Then it moves up from 1 -- checking membership and whether it divides appropriately.

Python 3, 96 bytes

n=int(input())
a=[]
for L in range(1,n+1):
t=L-sum(a)%L
while t in a:t+=L
a+=[t]
print(a[-1])


Ideone it!

JavaScript (ES6), 69 bytes

n=>{for(a=[],s=i=0;i++<n;a[j]=1,s+=j)for(j=i-s%i;a[j];)j+=i;return j}


At each stage just checks all the numbers with the appropriate remainder until it finds one that it hasn't seen before, then marks it seen and updates the total.

Behaviour, 64 bytes

c=&[(~!a{})(l=c:a-1s=0\(~(l<=s+=1)~!(l+s>&a+b)%a)l+s)]f=&(!c)%-1


Test with:

f:1
f:2
f:10


Calculates the list recursively and doesn't even work for n > 300, but you know, there was an attempt.

Ungolfed and commented:

// There are two functions, the first is recursive and creates the entire list
createList = &
[
(~!a; {})    // Base case, n==0 return empty list
(
list = createList:a-1 // create the list for n-1
smallest = 0          // initialize the variable to find the smallest
// Repeat the following Sequencer until success
\(
// Increments smallest and check if it is NOT on the list
~(list <= smallest+=1)

// sum up the list with the smallest found
sum = list+smallest > &a+b

// is the sum divided by n remainder 0
~!sum%a
)
// returns the list with the smallest
list + smallest
)
]
// The second function just execute the first and return its last item
f = &(!createList)%-1