19
\$\begingroup\$

I define mousetail's sequence as follows:

  • If the nth element of the sequence is q, then n+1 must appear q times in the sequence
  • The sequence is weakly monotonically increasing (i.e. no lower number may follow a higher number)
  • f(1)=1

I'll show an example of how this works:

  • the first element is 1
  • after the 1, come 1 2s
  • then 2 3s, since f(2)=2
  • then three 4s and three 5s, since f(3)=f(4)=3
  • then four 6s, four 7s, four 8s, five 9s, five 10s, and five 11s
  • six 12s, six 13s six 14s, six 15s, seven 16s etc.

Thus, it comes out to be

1,2,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9,9,10,10,10,10,10,11,11,11,11,11,12,12,12,12,12,12,13,13,13,13,13,13,14,14,14,14,14,14,...

Sequence rules apply, you may either:

  • Given n, output the nth element of the sequence
  • Given n, output the first n terms
  • Output the sequence infinitely

Either 0 or 1 based indexing is acceptable.

\$\endgroup\$
7
  • 5
    \$\begingroup\$ I found a somewhat interesting sequence not in the OEIS so it seemed time to paste my name onto it \$\endgroup\$
    – mousetail
    Jan 14 at 20:37
  • 3
    \$\begingroup\$ When you say "output the sequence up to N", do you mean "first n terms" or "terms whose values are not greater than n"? \$\endgroup\$
    – Neil
    Jan 14 at 21:20
  • \$\begingroup\$ This function is VERY close to \$1.2 n^{\phi - 1}\$ - this might allow for an explicit formula \$\endgroup\$ Jan 15 at 6:41
  • \$\begingroup\$ That \$1.2\$ constant is a bit surprising, I expected it to be \$\sqrt \phi\$, which is close, but a bit off. Perhaps the convergence is very slow? \$\endgroup\$ Jan 15 at 7:12
  • 6
    \$\begingroup\$ @CommandMaster This sequence is very similar to OEIS A001462, according to the OEIS entry the constant is \$\phi^{2-\phi}\$ which is approximately 1.201 \$\endgroup\$
    – bsoelch
    Jan 15 at 7:14

21 Answers 21

10
\$\begingroup\$

JavaScript (ES6), 29 bytes

This is based on the recurrence formula given for A001462, which is a very similar sequence found by bsoelch.

Returns the \$n\$-th term, 1-indexed.

f=n=>n<3?n:1+f(n-f(f(n-1)-1))

Try it online!

Formula

$$\begin{cases}a(1)=1\\ a(2)=2\\ a(n)=1+a(n-a(a(n-1)-1)),\:n\ge 3\end{cases}$$


JavaScript (ES6), 36 bytes

This is my original answer. Longer but faster.

Returns the \$n\$-th term, 0-indexed.

f=(n,i=0,k)=>i<n?f(n,i+f(k),-~k):-~k

Try it online!

Method

We don't need to store the sequence explicitly. We just have to keep track of the current position \$i\$ and current value \$k\$, and use recursion to get the previous values.

Commented

f = (         // f is a recursive function taking:
  n,          //   n = input
  i = 0,      //   i = current index
  k           //   k = current value, minus 1
) =>          //
i < n ?       // if i is less than n:
  f(          //   do a recursive call:
    n,        //     pass n unchanged
    i + f(k), //     add f(k) to i
    -~k       //     increment k
  )           //   end of recursive call
:             // else:
  -~k         //   return k + 1
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Maybe your third line of formula is $a(n)=\dots$? I feel it disagrees with your code. \$\endgroup\$
    – tsh
    Jan 16 at 9:43
7
\$\begingroup\$

K (ngn/k), 13 bytes

{(x#&0 1,)/x}

Try it online!

A function returning the first x values of the sequence.

(...)/x Iterate until convergence, starting with x (could be any non-negative integer):
0 1, Prepend 0 and 1 to the current list.
& Where. For boolean vectors this gives the indices of 1s, for positive integers each index is repeated by the value.
x# Take the first x values from the resulting list.

\$\endgroup\$
6
\$\begingroup\$

Python, 40 38 bytes

-1 thanks to @Mukundan314, additional -1 thanks to @JonathanAllan

f=lambda x:x*(x<3)or-~f(x-f(f(x-1)-1))

A port of @Arnauld's Javascript solution.

Attempt This Online!

Python, 62 bytes

def f():
 yield 1
 for i,x in enumerate(f()):yield from[i+2]*x

Attempt This Online!

\$\endgroup\$
3
  • \$\begingroup\$ -1 byte \$\endgroup\$ Jan 15 at 13:12
  • 1
    \$\begingroup\$ 38 bytes: x<3and x or -> x*(x<3)or \$\endgroup\$ Jan 15 at 18:19
  • \$\begingroup\$ +1 for using yield from in codegolf :) \$\endgroup\$
    – movatica
    Jan 31 at 9:21
4
\$\begingroup\$

Python, 42 bytes

a=[i:=1]
for x in a:print(x);a+=[i:=i+1]*x

Attempt This Online!

\$\endgroup\$
3
\$\begingroup\$

Jelly, 9 bytes

1Jx$Ż‘Ɗ¡ḣ

A monadic Link that accepts an integer, \$n\$, and yields a list of the first \$n\$ terms.

Try it online! Very inefficient! Remove to see the terms found before heading to \$n\$.

How?

1Jx$Ż‘Ɗ¡ḣ - Link: non-negative integer, Terms (n)
1         - set the left argument, Current, to one
       ¡  - repeat {Terms} times:
      Ɗ   -   last three links as a monad - f(Current):
   $      -     last two links as a monad - f(Current):
 J        -       range of length
  x       -       times {Current} (repeat indices by Current values respectively)
    Ż     -     prefix a zero
     ‘    -     increment
        ḣ - head to index {Terms}
\$\endgroup\$
0
2
\$\begingroup\$

Haskell, 39 30 bytes

Thanks to ovs

w=1:do n<-[0..];n+2<$[1..w!!n]

Try it online!

Constructs the list as a fixed point.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Directly generating the right numbers instead repeatedly incrementing allows to get rid of the function: w=1:do n<-[0..];n+2<$[1..w!!n] \$\endgroup\$
    – ovs
    Jan 14 at 22:22
2
\$\begingroup\$

Uiua 0.8.0, 22 bytes SBCS

⊡:⍥(⊂:↯⊃⊡(+1)⊢⇌..),0_1

Try on Uiua Pad! Takes an integer \$n\$ and returns the \$n\$th term.

Explanation

0_1 # array [0,1]
,   # duplicate input to top of stack
⍥(  # repeat n times
  .. # dup list twice
  ⊢⇌ # last element
  ⊃⊡(+1) # fork: get both the element at that index of the list and last element + 1
  ↯ # reshape: repeat last + 1 that many times
  ⊂: # join the array to the end
) 
⊡: # pick the nth element
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 10 8 bytes

2Ýλè<₅₆>

Outputs the 1-based \$n^{th}\$ value.

Try it online or verify the infinite sequence.

Explanation:

Uses the following recursive 0-based sequence to output the 1-based \$n^{th}\$ term:

$$a(0)=0, a(1)=1, a(2)=2\\ a(n)=a(n-a(a(n-1)-1))+1$$

  λ       # Start a recursive environment
   è      # to output the 0-based (implicit) input'th term
          # (which is output implicitly at the end)
2Ý        # Starting with a(0)=0, a(1)=1, and a(2)=2
          # And where every following a(n) is calculated as:
          #  (implicitly push a(n-1)):                  a(n-1)
    <     #  Decrease it by 1:                          a(n-1)-1
     ₅    #  Pop and take that term:                  a(a(n-1)-1)
      ₆   #  Pop and take the (n-value)'th term:  a(n-a(a(n-1)-1))
       >  #  And increase that by 1:              a(n-a(a(n-1)-1))+1
\$\endgroup\$
3
  • \$\begingroup\$ I find it a bit confusing that the absolute value appears in the formula. My understanding is that you only need it on the 05AB1E side because of the way the formula is implemented. But what you really do is \$n-a(a(n-1)-1)\$, right? \$\endgroup\$
    – Arnauld
    Jan 15 at 16:05
  • 1
    \$\begingroup\$ @Arnauld Yeah, that's indeed right. is 1 byte shorter than Ns- (where s is a swap of the top two values). I'll clarify it in my answer. \$\endgroup\$ Jan 15 at 23:45
  • 1
    \$\begingroup\$ @Arnauld The absolute difference is now gone completely after my latest golf.. I completely forgot there was the recursive a(n-x) builtin , which is exactly what we want here.. \$\endgroup\$ Jan 16 at 10:14
1
\$\begingroup\$

Scala 3, 96 bytes

A port of @Command Master's Python code in Scala.


Golfed version. Attmept This Online!

def f():Iterator[Int]=Iterator(1)++f().zipWithIndex.flatMap{case(x,i)=>Iterator.fill(x)(i+2)}  

Ungolfed version. Attempt This Online!

object Main {
  def main(args: Array[String]): Unit = {
    f().take(100).foreach(x => print(s"$x "))
  }

  def f(): Iterator[Int] = Iterator(1) ++ f().zipWithIndex.flatMap { case (x, i) =>
    Iterator.fill(x)(i + 2)
  }
}


// 1
// 1 2                  // append 1 number.two
// 1 2 3 3              // append 2 number.three
// 1 2 3 3 4 4 4 5 5 5  // append 3 number.four  append 3 number.five
//...                   
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 20 19 bytes

FN⊞υ∨¬υ⊕§υ±§υ⁻⌈υ²Iυ

Try it online! Link is to verbose version of code. Outputs the first n values. Explanation: Adapted my efficient answer to use @Arnauld's recurrence relation.

FN

Repeat n times.

⊞υ∨¬υ⊕§υ±§υ⁻⌈υ²

Push 1 as the first value, otherwise use the recurrence relation. Charcoal's cyclic indexing allows this to work for n=2 as a degenerate case since there is only one value in the array at this point.

Iυ

Output the n results.

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

Google Sheets, 62 bytes

=let(f,lambda(f,n,if(n<3,n,1+f(f,n-f(f,f(f,n-1)-1)))),f(f,A1))

Put \$n\$ in cell A1 and the formula in cell B1. The output is the \$n\$th term.

Using the recursive function in Arnauld's JavaScript answer. Google Sheets supports recursion to a depth of 10,000 but the calculation limit is met much earlier here because the function branches several times. The formula will start erroring out at \$n\$ = 34.

This iterative implementation will handle much bigger values of \$n\$ (75 bytes):

=reduce(,sequence(A1),lambda(a,n,iferror({a;sequence(index(a,n),1,n,)},1)))

Put \$n\$ in cell A1 and the formula in cell B1. Output appears in cells B2:B and contains elements up to and including the element whose value is \$n\$. To make the number of elements in the output limited to \$n\$ instead (99 bytes):

=array_constrain(reduce(...),A1+1,1)
\$\endgroup\$
2
  • \$\begingroup\$ The question was edited to clarify that it's the first n elements, not the elements up to the n value. \$\endgroup\$
    – Neil
    Jan 15 at 0:11
  • \$\begingroup\$ Yes... that adds some complexity. Edited the answer to include array_constrain(). \$\endgroup\$ Jan 15 at 10:53
1
\$\begingroup\$

Uiua SBCS, 12 bytes

↙:⍥(⊚⊂⇡2),[]

Try it!

Very inefficient. An adaptation of ovs' K answer. Returns the first n elements of the sequence.

↙:⍥(⊚⊂⇡2),[]
          []  # push empty list
         ,    # copy input to top of stack
  ⍥(    )     # repeat [input] times
      ⇡2      # push [0 1]
     ⊂        # prepend
    ⊚         # repeat each index [value] times
↙:            # take the first [input] values
\$\endgroup\$
1
\$\begingroup\$

Vyxal 3, 14 bytes

1Ọw{mvᵇiᵂ…YᵛỌJ

Try it Online!

1Ọw{mvᵇiᵂ…YᵛỌJ­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁣⁣‏⁠‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌­
1Ọw             # ‎⁡Output 1 without popping, wrap in list
   {            # ‎⁢While true
    mv          # ‎⁣ Decrement the current iteration n
      ᵇi        # ‎⁤ Index into list without popping
        ᵂ…      # ‎⁢⁡ Stash indexed item, add 2 to n-1 -> n+1, unstash item
          Y     # ‎⁢⁢ Repeat n+1 item at index n-1 times
           ᵛỌ   # ‎⁢⁣ Print each element without popping
             J  # ‎⁢⁤ Join repeated list with original list
💎

Created with the help of Luminespire.

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

R, 33 bytes

`?`=\(n)`if`(n<3,n,1+?n-?-1+?n-1)

Attempt This Online!

Port of @Arnauld's JavaScript answer.

R, 43 bytes

\(n)rep(seq(x<-c(1,1,rep(1:n,1:n-1))),x)[n]

Attempt This Online!

Straightforward generation of the sequence.

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

Ruby, 67 bytes

67 bytes, it can be golfed much more.


Golfed version. Try it online!

f=Enumerator.new{|y|y<<1;e=f.dup;i=2;loop{e.next.times{y<<i};i+=1}}

Ungolfed version. Try it online!

def f
  Enumerator.new do |yielder|
    yielder << 1
    enum = f
    i = 2
    loop do
      x = enum.next
      x.times { yielder << i }
      i += 1
    end
  end
end

f.lazy.take(100).each { |x| print "#{x} " }
\$\endgroup\$
1
\$\begingroup\$

TypeScript's type system, 113 bytes

//@ts-ignore
type G<N,I=[],O=[[1]],Z=[...I,1],S=O[I["length"]]>=I extends N?S:G<N,Z,[...O,...{[_ in keyof S]:Z}]>

Try it at the TypeScript playground! I/O is with unary numbers represented as tuples of 1s.

Or, 125 122 bytes with I/O as decimal numbers:

//@ts-ignore
type G<N,I=[],O=[[1]],L="length",Z=[...I,1],S=O[I[L]]>=I[L]extends N?S[L]:G<N,Z,[...O,...{[_ in keyof S]:Z}]>

Try it at the TypeScript playground

This keeps track of the sequence O, the requested entry N, and the current iteration number I. It continuously appends I + 1 repeated O[I] times to O, until I is equal to N, at which point O[N] (the Nth entry) is returned.

TypeScript's type system, 113 bytes

//@ts-ignore
type F<A,B="">=B extends`${A}${infer Z}`?Z:A extends"1"|"11"|"111"?A:`1${F<F<F<F<1,F<F<1,A>>>>,A>>}` 

I/O is unary numbers represented as string types of the character 1.

This is a port of Arnauld's JavaScript solution. It ends up pretty long in TypeScript because we don't have numeric comparison or subtraction built-in.

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

JavaScript (Node.js), 58 bytes

for(o=[0,j=i=1];;console.log(j=o[++i]))for(;j--;)o.push(i)

Attempt This Online!

I tried another approach, this one generates the sequence infinitely.

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

Japt, 14 13 bytes

<3?U:ÒßU´-ßÓß

Try it

-1 byte thanks to Shaggy

This uses the same method as Arnauld’s JavaScript solution, but it is rearranged slightly.

A direct port is 16 bytes:

<3?U:ßU-ßßUÉ É)Ä

Try it

This isn’t efficiently packed, though; there’s a space and a close parenthesis, which are generally good to try to avoid in Japt.

This is the obvious method, using the commonly used postfix decrement É (-1) and increment Ä (+1). Japt actually does have prefix equivalents for both of these, however: Ò (-~) for increment, and Ó (~-) for decrement. In this case, both of the parentheses can be omitted by using prefix operators.

The 16-byte version is the same as Arnauld’s:

f=n=>n<3?n:f(n-f(f(n-1)-1))+1

This version is closer to:

f=n=>n<3?n:-~f(n-f(~-f(n-1)))

where the trailing parentheses can be omitted in Japt.

Shaggy's suggestion changes that final -1 to an in-place decrement:

f=n=>n<3?n:-~f((n--)-f(~-f(n)))

The difference is that now, that argument to the final recursion can also be omitted, saving a byte.

\$\endgroup\$
3
  • \$\begingroup\$ 13 bytes \$\endgroup\$
    – Shaggy
    Jan 30 at 0:47
  • \$\begingroup\$ @Shaggy TIL recursion automatically passes U \$\endgroup\$
    – noodle man
    Jan 30 at 1:53
  • \$\begingroup\$ Also, I had the Japt chatroom unfrozen a little while ago, and sent you some ideas I had about a Japt successor, but I'm not sure if the ping went through so I'm letting you know here. \$\endgroup\$
    – noodle man
    Jan 30 at 1:59
1
\$\begingroup\$

Clean, 55 bytes

import StdEnv
w=[1: $0]
$s=[s+2\\_<-[1..w!!s]]++ $(s+1)

Try it online!

My first clean answer. Probably could be improved.

Clean, 59 bytes

import StdEnv
g[h:t]=[1\\_<-[1..h]]++[x+1\\x<-g t]
w=g[1:w]

Try it online!

This is an alternate approach. This feels very close to beating the other one, but I can't quite get it to work out.

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

Pip, 18 bytes

Fi,aoAL:i+2RL Po@i

Given an input a, outputs the first a terms. Attempt This Online!

Explanation

Fi,aoAL:i+2RL Po@i­⁡​‎‏​⁢⁠⁡‌⁢​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌­
                    ; ‎⁡a is command-line argument; o is 1 (implicit)
Fi,a                ; ‎⁢For i in range(a):
              Po@i  ; ‎⁣Print element of o at index i
        i+2RL       ; ‎⁤Make a list of that many copies of i+2
                    ; ‎⁤(It has to be i+2, not i+1, because Pip uses 0-indexing)
    oAL:            ; ‎⁢⁡Append that list to o
💎

Created with the help of Luminespire.

(Note that o is a scalar on the first iteration, but as soon as AL is used to append something to it, it gets converted to a list.)

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

Haskell + hgl, 17 bytes

w=jn$zW rl(1:w)nN

Attempt This Online!

Explanation

Like the my other Haskell answer this calculates the sequence as the fixed point of a function, however it implements that function pretty differently.

If the list is w then we zip 1:w with the natural numbers using rl, a function which repeats the input n times. Then we concat together the result.

Alternate solutions

w=jn$ixo 1frl$1:w

Attempt This Online!

yy$jn<ixo 1frl<K1

Attempt This Online!

Reflection

  • A couple days ago I mentioned wanting a function which zips and then concats. That would obviously be very useful here, but I still haven't implemented it.
  • There should be an infix version of zW.
  • ixo should have a version precomposed with small values. Maybe an infix function as well.
\$\endgroup\$

Your Answer

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

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