12
\$\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\$
1
  • 5
    \$\begingroup\$ Apart from the first 2 terms, this is the complement of A022433. \$\endgroup\$
    – Arnauld
    May 1, 2020 at 10:46

10 Answers 10

19
\$\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} } $$

\$\endgroup\$
1
  • \$\begingroup\$ The golfing force is strong in him! \$\endgroup\$
    – Kaddath
    May 4, 2020 at 11:31
4
\$\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
\$\endgroup\$
0
4
\$\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.
\$\endgroup\$
2
\$\begingroup\$

Husk, 16 bytes

!¡ȯ←`-NS+Sz+↓2ḋ3

Try it online!

Outputting the infinite list gives -1. Kinda sad I'm unable to get it below 16.

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

\$\endgroup\$
1
  • \$\begingroup\$ So sorry, thought that was my post - rolled back changes. \$\endgroup\$
    – Noodle9
    May 1, 2020 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

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

\$\endgroup\$
3
  • \$\begingroup\$ 42 bytes \$\endgroup\$
    – Arnauld
    May 1, 2020 at 19:24
  • \$\begingroup\$ @Arnauld Very nice - thanks! :-) \$\endgroup\$
    – Noodle9
    May 1, 2020 at 19:38
  • \$\begingroup\$ Darn, so close! \$\endgroup\$
    – S.S. Anne
    May 2, 2020 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!

\$\endgroup\$
4
  • 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\$ May 1, 2020 at 13:47
  • \$\begingroup\$ @KevinCruijssen Awesome squeeze - thanks! :D \$\endgroup\$
    – Noodle9
    May 1, 2020 at 15:38
  • \$\begingroup\$ 42 bytes \$\endgroup\$
    – Arnauld
    May 1, 2020 at 22:20
  • \$\begingroup\$ @Arnauld Clever - thanks! :-) \$\endgroup\$
    – Noodle9
    May 1, 2020 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!

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

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