9
\$\begingroup\$

The skip-pure numbers are defined with this rule:

A(0) = 1
A(1) = 1
A(n) = the smallest positive number not in the sequence such that A(x) + A(x-2) for any x never appears

For example, the term A(2) is 2, because 1 has already appeared. The term A(3) is 4, as A(2) + A(0) = 3 and 3 is disallowed by the third line of the rule.

Given a number n, your program should output the nth skip-pure number, using zero-based indexing (such that A(0) is defined).

Output can be in any format (strings, ints, lists, arrays, etc.), but the number itself must be outputted in base 10.

Trailing output (newlines, etc.) is allowed but only if your language has to output it. If you can work around trailing output, solve it with the workaround.

Here are test cases, shown in the format input = output:

0 = 1
1 = 1
2 = 2
3 = 4
4 = 6
5 = 7
6 = 9
7 = 10
8 = 12
9 = 13

I created this sequence myself and am probably the first person to talk about it, so there is no OEIS link.

This is a code-golf, so the shortest program that does all of the above (measured in bytes) wins. Have fun.

\$\endgroup\$
  • 4
    \$\begingroup\$ Apart from the first 2 terms, this is the complement of A022433. \$\endgroup\$ – Arnauld May 1 at 10:46
16
\$\begingroup\$

JavaScript (ES7),  59  31 bytes

Returns the \$n\$-th term, 0-indexed. This is a closed-form formula.

n=>n*1.5^Math.log2(n)&n%4==2^!n

Try it online!

Formula

The only edge case is \$a(0)=1\$. For \$n\ge1\$:

$$a(n)=\cases{\left\lfloor\dfrac{3n}{2}\right\rfloor-1,&\text{if $\lfloor log_2(n)\rfloor$ is odd and $n\equiv 2\pmod 4$} \\ \left\lfloor\dfrac{3n}{2}\right\rfloor,&\text{otherwise} } $$

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The golfing force is strong in him! \$\endgroup\$ – Kaddath May 4 at 11:31
3
\$\begingroup\$

Haskell, 68 bytes

a n|n<2=1|q<-n-1=[x|x<-[a q+1..],notElem x[a c+a(c-2)|c<-[2..q]]]!!0

Try it online!

Pretty simple answer, doesn't use the formula since that is no fun.

a n                   -- a n is ...
  |n<2=1              -- 1 if n less than 2
  |q<-n-1=            -- where q is n-1
    [...]!!0          -- the first element of ...
      x|x<-[a q+1..], -- the integers larger than a(n-1) such that ...
        notElem x[a c+a(c-2)|c<-[2..q]]
          -- it satisfies the condition in the challenge.
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 20 17 16 13 bytes

‚Qλè∞λЦ¦+«Kн

-3 bytes by porting @Arnauld's JavaScript answer, so make sure to upvote him!
-6 bytes on my original 20 bytes solution thanks to @Grimmy, making it shorter than the port

Outputs the 0-based \$n^{th}\$ value, as specified in the challenge description.

Try it online.

Outputting the infinite sequence would be 12 bytes:

1‚λ∞λЦ¦+«Kн

Try it online.

And outputting the first \$n\$ values of the sequence would be 13 bytes again:

‚Qλ£∞λЦ¦+«Kн

Try it online.

Explanation:

‚              # Pair the (implicit) input with itself
 Q             # Check for each whether it's equal to the (implicit) input
               # which results in a pair of 1s: [1,1]
  λ            # Create a recursive environment
   è           # to output the 0-based n'th value, where n is the (implicit) input
               # (which will be output implicitly at the end)
               # Starting with a(0)=a(1)=1 due to the earlier [1,1]-pair
               # And for any other a(n) we'll:
    ∞          #  Push an infinite positive list: [1,2,3,...]
     λ         #  Push a list of all previous values: [a(0),a(1),...,a(n-1)]
      Ð        #  Triplicate that list
       ¦¦      #  Remove the first two values from the top copy
         +     #  Add the values in the top two lists together at the same positions,
               #  which also shortens the longer list by two:
               #  [a(0)+a(2),a(1)+a(3),...,a(n-3)+a(n-1)]
          «    #  Merge it to the remaining copy of the triplicate
           K   #  Remove all those values from the infinite positive list
            н  #  Pop and leave the first remaining positive integer

1‚             # Pair 1 with itself (only works if there is no input,
               # in which case it uses the 1 again implicitly)
  λ            # Create a recursive environment
               # to output the infinite list
   ∞λЦ¦+«Kн   #  The rest is the same as above
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Python 2, 76 bytes

a=b=1
w=s={1}
exec"w|=s;c=b;b=a\nwhile w&s:a+=1;s={a,a+c}\n"*input()
print b

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ So sorry, thought that was my post - rolled back changes. \$\endgroup\$ – Noodle9 May 1 at 12:25
1
\$\begingroup\$

Japt, 17 bytes

Direct port of Arnauld's formula so be sure to +1 him.

*1½^MmU &U%4¥2^!U

Try it

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 58 42 bytes

Using Arnauld's formula from his JavaScript answer.

Saved a whopping 16 bytes thanks to the man himself Arnauld!!!

f(n){n=3*n/2^~__builtin_clz(n)&n%4==2^!n;}

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 42 bytes \$\endgroup\$ – Arnauld May 1 at 19:24
  • \$\begingroup\$ @Arnauld Very nice - thanks! :-) \$\endgroup\$ – Noodle9 May 1 at 19:38
  • \$\begingroup\$ Darn, so close! \$\endgroup\$ – S.S. Anne May 2 at 15:50
1
\$\begingroup\$

Python 2, 75 \$\cdots\$ 44 42 bytes

Using Arnauld's formula from his JavaScript answer.

Saved 2 5 8 bytes thanks to Kevin Cruijssen!!!
Saved a whopping 8 22 23 25 bytes thanks to the man himself Arnauld!!!

lambda n:0**n^3*n/2^(len(bin(n))%2|n%4==2)

Try it online!

Using the OP's formula

Python 3, 87 86 bytes

f=lambda n,r=[1,1],i=1:i*(len(r)/2>=n)or(i in r)and f(n,r,i+1)or f(n,[i]+r+[i+r[1]],i)

Try it online!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 45 bytes by using a similar thing I did in my 62-byter on @Arnauld's 48-byter. (You also forgot to change the header to Python 2.) \$\endgroup\$ – Kevin Cruijssen May 1 at 13:47
  • \$\begingroup\$ @KevinCruijssen Awesome squeeze - thanks! :D \$\endgroup\$ – Noodle9 May 1 at 15:38
  • \$\begingroup\$ 42 bytes \$\endgroup\$ – Arnauld May 1 at 22:20
  • \$\begingroup\$ @Arnauld Clever - thanks! :-) \$\endgroup\$ – Noodle9 May 1 at 23:49
1
\$\begingroup\$

Io, 75 bytes

Port of Arnauld's formula from their JS answer.

method(n,(3*n/2)floor-if((n log2 floor%2==0)and(n%2==4),-1,0)+if(n==0,1,0))

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

R, 43 42 40 bytes

Using the same formula as earlier answers (and Robin's suggestions)

n+(n/2)%/%1-(!n%%4-2&log2(n+.1)%%2>1)+!n

Try it online!

| improve this answer | |
\$\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.