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\$
8
  • \$\begingroup\$ What values of n and a(n) must we support? \$\endgroup\$ Aug 18, 2016 at 1:42
  • \$\begingroup\$ @RohanJhunjhunwala Theoretically every positive number. \$\endgroup\$
    – Leaky Nun
    Aug 18, 2016 at 1:44
  • \$\begingroup\$ so bignum mandatory? \$\endgroup\$ Aug 18, 2016 at 1:47
  • \$\begingroup\$ @RohanJhunjhunwala I said theoretically, meaning it is not mandatory. \$\endgroup\$
    – Leaky Nun
    Aug 18, 2016 at 1:47
  • 1
    \$\begingroup\$ Strangely related. \$\endgroup\$
    – xnor
    Aug 18, 2016 at 4:07

9 Answers 9

13
\$\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\$
8
  • \$\begingroup\$ I think the precision is fine up to 2**32. \$\endgroup\$
    – xnor
    Aug 18, 2016 at 4:27
  • \$\begingroup\$ Then it does not work outside the boundary. \$\endgroup\$
    – Leaky Nun
    Aug 18, 2016 at 4:28
  • \$\begingroup\$ @LeakyNun I thought you said up to 2^31 -1 is ok? \$\endgroup\$
    – xnor
    Aug 18, 2016 at 4:30
  • \$\begingroup\$ What does it return for 2^31-1? \$\endgroup\$
    – Leaky Nun
    Aug 18, 2016 at 4:34
  • \$\begingroup\$ @LeakyNun It gives 6949403065.0. \$\endgroup\$
    – xnor
    Aug 18, 2016 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\$
3
  • \$\begingroup\$ Can you remove the whitespace after the last in? \$\endgroup\$
    – Leaky Nun
    Aug 18, 2016 at 6:28
  • \$\begingroup\$ I'm guessing you meant before? Thanks for editing in the demo! \$\endgroup\$
    – m-chrzan
    Aug 18, 2016 at 6:38
  • \$\begingroup\$ Yes, I meant before \$\endgroup\$
    – Leaky Nun
    Aug 18, 2016 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\$
9
  • \$\begingroup\$ Use a while loop for the second nested loop. Your solution currently does not theoretically support higher integers. \$\endgroup\$
    – Leaky Nun
    Aug 18, 2016 at 2:38
  • \$\begingroup\$ Rather than using 4 spaces, you can use a tab or one space. \$\endgroup\$
    – Leaky Nun
    Aug 18, 2016 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, 2016 at 2:48
  • \$\begingroup\$ Make sure to include your byte count. \$\endgroup\$
    – Leaky Nun
    Aug 18, 2016 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, 2016 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\$
2
\$\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\$
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\$
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\$
0
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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