5
\$\begingroup\$

Task

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

\$\endgroup\$
  • \$\begingroup\$ What values of n and a(n) must we support? \$\endgroup\$ – Rohan Jhunjhunwala Aug 18 '16 at 1:42
  • \$\begingroup\$ @RohanJhunjhunwala Theoretically every positive number. \$\endgroup\$ – Leaky Nun Aug 18 '16 at 1:44
  • \$\begingroup\$ so bignum mandatory? \$\endgroup\$ – Rohan Jhunjhunwala Aug 18 '16 at 1:47
  • \$\begingroup\$ @RohanJhunjhunwala I said theoretically, meaning it is not mandatory. \$\endgroup\$ – Leaky Nun Aug 18 '16 at 1:47
  • \$\begingroup\$ so less than 2^31 -1 is ok? \$\endgroup\$ – Rohan Jhunjhunwala Aug 18 '16 at 1:49
12
\$\begingroup\$

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.

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

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.

\$\endgroup\$
  • \$\begingroup\$ Can you remove the whitespace after the last in? \$\endgroup\$ – Leaky Nun Aug 18 '16 at 6:28
  • \$\begingroup\$ I'm guessing you meant before? Thanks for editing in the demo! \$\endgroup\$ – m-chrzan Aug 18 '16 at 6:38
  • \$\begingroup\$ Yes, I meant before \$\endgroup\$ – Leaky Nun Aug 18 '16 at 6:39
3
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ Use a while loop for the second nested loop. Your solution currently does not theoretically support higher integers. \$\endgroup\$ – Leaky Nun Aug 18 '16 at 2:38
  • \$\begingroup\$ Rather than using 4 spaces, you can use a tab or one space. \$\endgroup\$ – Leaky Nun Aug 18 '16 at 2:48
  • \$\begingroup\$ You can also use space for the first level and then tab for the second level. \$\endgroup\$ – Leaky Nun Aug 18 '16 at 2:48
  • \$\begingroup\$ Make sure to include your byte count. \$\endgroup\$ – Leaky Nun Aug 18 '16 at 2:48
  • \$\begingroup\$ 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. \$\endgroup\$ – Leaky Nun Aug 18 '16 at 3:01
2
\$\begingroup\$

Pyth - 23 21 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

Try it online here.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.