Golomb's wobbly sequence

Question

OEIS has a variation (A111439) on Golomb's sequence. As in Golomb's sequence, A(n) describes how often n appears in the sequence. But in addition, no two consecutive numbers may be identical. While building up the sequence, A(n) is always chosen as the smallest positive integer that doesn't violate these two properties. Due to disallowed consecutive identical numbers, the series wobbles slightly up and down as it grows. Here are the first 100 terms:

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 5, 6, 5, 6, 7, 6, 7, 8, 7, 8, 9, 8, 9, 8, 9, 
10, 9, 10, 9, 10, 11, 10, 11, 10, 11, 10, 11, 12, 11, 12, 13, 12, 13, 12, 
13, 12, 13, 12, 13, 14, 15, 14, 15, 14, 15, 14, 15, 14, 15, 14, 15, 16, 15, 
16, 17, 16, 17, 16, 17, 16, 17, 16, 17, 18, 17, 18, 17, 18, 19, 18, 19, 18, 
19, 18, 19, 18, 19, 18, 19, 20, 19, 20, 21, 20, 21, 20, 21, 20, 21, 20

The full list of the first 10,000 numbers can be found on OEIS.

The challenge is to write a program or function which computes A(n), given n. n is 1-based to ensure that the self-describing property works.

Rules

You may write a program or a function and use any of the our standard methods of receiving input and providing output.

You may use any programming language, but note that these loopholes are forbidden by default.

This is code-golf, so the shortest valid answer – measured in bytes – wins.

Test Cases

n     A(n)
1     1
4     2
10    6
26    10
100   20
1000  86
1257  100
10000 358

Answer 1

Haskell, 67 bytes

f k|k<4=k|p<-k-1=[n|n<-[1..],n/=f p,sum[1|a<-[1..p],f a==n]<f n]!!0

Defines a function f. Try it online! It's very slow, computing f 15 times out on TIO.

Explanation

Just going with the definition: at every stage, choose the minimal positive number n that satisfies the constraints (not equal to previous entry, and has not occurred f n times yet).

f k             -- Define f k:
 |k<4=k         -- If k < 4, it's k.
 |p<-k-1=       -- Otherwise, bind k-1 to p,
  [n|           -- compute the list of numbers n where
   n<-[1..],    -- n is drawn from [1,2,3,...],
   n/=f p,      -- n is not equal to f p, and
   sum[1|       -- the number of
    a<-[1..p],  -- those elements of [1,2,3,...,p]
    f a==n]     -- whose f-image equals n
   <f n]        -- is less than f n,
  !!0           -- and take the first element of that list.

Answer 2

Mathematica, 69 68 bytes

Thanks to Martin Ender for finding an extra –1 byte for me!

Last@Nest[{##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&,{},#]&

Unnamed function taking a positive integer n as input and returning a positive integer. We construct the entire list of the first n elements of this sequence, then take the Last element. The list is constructed by starting with the empty list {} and operating on it with a function n times in a row (via Nest).

The function in question is {##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&, which takes a partial list of sequence values (essentially ##&@@#) and appends the next value to it. The next value is computed by starting with x=1, then repeatedly replacing x by x+1 as long as the condition x==Last@#||#~Count~x==#[[x]] is met—in other words, if either x is the previous element, or else x is already in the list the correct number of times. This function spits some errors, since (for example) we shouldn't be calling the xth element of the initial list {}; however, the values are all correct.

Answer 3

Python 2, 99 86 bytes

Thanks to @Dennis for several improvements totaling 13 bytes!

s=0,1,2,3
exec't=1\nwhile t==s[-1]or s.count(t)/s[t]:t+=1\ns+=t,;'*input()
print s[-4]

The program proceeds pretty naively: It keeps track of the list of values it's determined so far, and looks to append the next value. It tries to append a 1 to the end of the list if it can; if not, then it tries a 2 and so on until something is allowed.

Now, we start by seeding the results for 1,2,3 to be 1,2,3. This is done to avoid any problems with the list of already-computed values being too short: I conjecture that if n is at least 4 then a(n) is strictly less than n. (In this program, s[n] is equal to a(n). Our list actually is initialized to be [0,1,2,3] because lists are 0-indexed in Python. So for instance a(1)=s[1]=1, and a(2)=s[2]=2.)

So, let's say we're trying to determine s[m], meaning that our list already includes s[0], s[1], ..., s[m-1]. We'll start at t=1 and try to set s[m]=1. When that doesn't work, we go to t=2 and try to set s[m]=2. Each time we increment t, we check whether s.count(t)==s[t]...but the right-hand side won't produce an error so long as we never have to go as high as t=m. The conjecture says that we never have to, since the first value we compute is actually s[4].

This implementation computes 3 more values of the sequence than it needs to. For example if n is 8, it'll compute up through s[11] before it returns the value of s[8].

I'd be happy to see a proof of the conjecture. I believe it can be proven by (strong?) induction.

Edit: Here is a proof of the conjecture. We actually prove a slightly stronger form of the statement, since it involves no extra work.

Theorem: For all n greater than or equal to 4, the term a(n) is less than or equal to (n-2).

Proof (by Strong Induction): (Base n=4): The statement is true for n=4, since a(4) = 2 = 4-2.

Now assume a(k) is less than or equal to k-2 for all k from 4 through n, inclusive (and assume n is at least 4). In particular, this means that all previous terms of the sequence were at most (n-2). We need to show that a(n+1) will be at most (n-1). Now, by definition, a(n) is the smallest positive integer that doesn't violate any of the conditions, so we just need to show that the value (n-1) will not violate any of the conditions.

The value (n-1) will not violate the "no consecutive repeats" condition, because by the induction hypothesis the previous entry was at most (n-2). And it won't violate the "a(m) is the number of times m appears" condition, unless (n-1) had already been reached a(n-1) times. But by the strong induction assumption, (n-1) had previously been reached 0 times, and a(n-1) is not equal to 0 since a(m) is positive for all m.

Therefore a(n+1) is less than or equal to n-1 = (n+1)-2, as desired. QED.

Answer 4

Jelly, 17 bytes

Ṭ€S<;1Tḟ®Ḣ©ṭ
⁸Ç¡Ṫ

The last three test cases are too much for TIO. I've verified 1000 and 1257 locally.

Try it online! or verify the first 100 terms.

How it works

⁸Ç¡Ṫ          Main link. No arguments.

⁸             Yield [].
 Ç¡           Execute the helper link n times (where n is an integer read from
              STDIN), initially with argument [], then with the previous return
              value as argument. Yield the last return value.
              Tail; yield the last element of the result.


Ṭ€S<;1Tḟ®Ḣ©ṭ  Helper link. Argument: A (array)

Ṭ€            Untruth each convert each k into an array of k-1 zeroes and one 1.
  S           Sum; column-wise reduce by +, counting the occurrences of all
              between 1 and max(A).
   <          Compare the count of k with A[k] (1-indexed), yielding 1 for all
              integers that still have to appear once or more times.
    ;1        Append a 1 (needed in case the previous result is all zeroes).
      T       Truth; find all indices of ones.
       ḟ®     Filter-false register; remove the value of the register (initially 0)
              from the previous result.
         Ḣ©   Head copy; yield the first (smallest) value of the result and save
              it in the register.
           ṭ  Tack; append the result to A.

Answer 5

Python 2, 77 74 bytes

f=lambda n,k=1:n*(n<4)or map(f,range(n)+k*[n-1]).count(k)<f(k)or-~f(n,k+1)

This is a recursive implementation of @mathmandan's algorithm.

The implementation is O(insane): input 9 takes 2 seconds locally, input 10 52 seconds, and input 11 17 minutes and 28 seconds. However, if declared as a regular function rather than a lambda, memoization can be used to verify the test cases.

Try it online!

Note that even with memoization, TIO cannot compute f(1257) or f(10000) (both verified locally).

Answer 6

05AB1E, 32 31 bytes

XˆXˆG[N¯2(è<›¯¤NÊsN¢¯Nè‹&&#]N.ˆ

Try it online!

Explanation

XˆXˆ                             # initialize global list as [1,1]
    G                            # input-1 times do:
     [                    #]     # loop until expression is true     
      N¯2(è<›                    # n > list[-2]-1
             ¯¤NÊ                # list[-1] != N
                 sN¢¯Nè‹         # count(list, N) < list[N]
                        &&       # logical AND of the 3 expressions
                            N.ˆ  # add N to global list 
                                   and output last value in list and end of program

We are technically in loop G when we add N to global list, but all loops in 05AB1E use the same variable N as index, so the inner loop [...] has overwritten the N of G meaning we can add it outside the loop.

Issues with nested loops and conditionals prevents us from doing this inside the loop.

Answer 7

Befunge, 141 136 bytes

<v9\0:p8\2:*2:-1<9
v>p1+:3\8p0\9p:#^_&
>1-:#v_1.@>$8g.@
*+2%\>1-:!|>$!:::9g!\!9g!*\:8g\!8g`
9\+1g9::< \|`g9\g8+2::p
g2+\8p2+^:<>:0\9p::8

Try it online!

Because of Befunge's memory limitations, it's not really practical to keep track of all previous entries entries in the sequence, so this solution uses an algorithm with a lower memory footprint which calculates the values more directly.

That said, we're still limited by the cell size, which in the Befunge-93 reference interpreter is a signed 8-bit value, so the highest supported even number in the sequence is A(1876) = 126, and the highest supported odd number is A(1915) = 127.

If you want to test larger values, you'll need to use an interpreter with a larger cell size. That should include most Befunge-98 implementations (Try it online!).

Answer 8

Husk, 18 bytes

!¡λḟ≠→¹f§<!#¹ŀΘ)ḣ3

Try it online!

I decided to spare my soul and do it without combinators, and it's still the same size with them. Fun sequence.

^{just need to save a single byte...}

Explanation

!¡λḟ≠→¹f§<!#¹ŀΘ)ḣ3
                ḣ3 start with [1,2,3]
 ¡λ            )   apply the following repeatedly:
             ŀΘ    prepend zero, get range [1..length+1]
                   → [1,2,3,4]
       f§          filter out values where:
           #¹      frequency in sequence     
         <         is not less than
          ! ¹      projected frequency in sequence
                   → [2,3]
   ḟ               find the first element
    ≠→¹            which isnt equal to the most recent element
                   → 2
!                  take the nth element of this infinite list

Answer 9

Python 2, 117 bytes

Meh. Not that short. The simple iterative solution.

L=[1,2,3]
n=input()
while len(L)<n:
 for i in range(2,n):
    if L.count(i)<L[i-1]and L[-1]!=i:L+=[i];break
print L[n-1]

Try it online

Here's a really bad attempt at a recursive solution (129 bytes):

def f(n,L=[1,2,3]):
 if len(L)>=n:print L[n-1];exit(0)
 for i in range(2,n):
    if L.count(i)<L[i-1]and L[-1]!=i:f(n,L+[i])
 f(n,L)