16
\$\begingroup\$

Gobar primes (A347476) are numbers which give a prime number when 0's and 1's are interchanged in their binary representation.

For example, \$10 = 1010_2\$, and if we flip the bits, we get \$0101_2 = 5\$ which is prime. Therefore, 10 is a Gobar prime

As simple as that: print the series with any delimiter. Shortest code wins.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Do we need to print the series, or can we use the normal sequence rules (taking an index as input and printing that item)? Also, I'd recommend using the sandbox for future challenges, it helps a lot! \$\endgroup\$ Commented Oct 22, 2021 at 13:52
  • \$\begingroup\$ @RedwolfPrograms print the series BTW index one could be proposed right? \$\endgroup\$
    – Ha'Penny
    Commented Oct 22, 2021 at 13:53
  • 7
    \$\begingroup\$ You might want to check out the default sequence rules, those are what most challenges allow. \$\endgroup\$ Commented Oct 22, 2021 at 13:58
  • \$\begingroup\$ Weird to call those numbers (Gobar) primes when only one of them is prime \$\endgroup\$
    – Luis Mendo
    Commented Oct 22, 2021 at 16:35
  • 3
    \$\begingroup\$ The sequence rules for I/O (choose to either output the nth, first n or all) do apply by default to [sequence] challenges, but I would suggest clarifying that in the post \$\endgroup\$ Commented Oct 22, 2021 at 16:48

15 Answers 15

4
\$\begingroup\$

Vyxal 5, 6 bytes

∞'b⌐Bæ

Try it Online!

this just times out, so not sure if it is valid

∞   # All positive integers
'       # filter by
b      # binary
⌐      # Minus from 1, (1-1=0, 1-0=1, genius)
B     # decimal
æ    # is prime?

Vyxal 5, 8 bytes

∞ƛb⌐Bæß,

Try it Online!

This one actually prints everything (remove the 5 flag to run for more time)

pseudo code

all positive integers
map
  binary representation
  subtract each bit from 1 aka complement
  back to decimal
  is prime
  if truthy
    print
  (implicit else)
    (implicit continue)
(implicit end map)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Probably don't put 5 in the header if you're just using it to keep it from infinitely looping \$\endgroup\$ Commented Oct 22, 2021 at 16:40
4
\$\begingroup\$

C (gcc), 96 94 bytes

k;i;d;p;f(n){for(i=5;n;n-=p)for(k=i++^(1<<32-__builtin_clz(i))-1,d=p=k>1;++d<k;)p=p&&k%d;--i;}

Try it online!

Returns the zero-based \$n^\text{th}\$ Gobar prime.

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

JavaScript (V8), 48 bytes

for(i=k=j=0;;)j%k%++i?1:~i?i=++k-(j|=k):print(k)

Try it online!

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

Ruby, 46 45 bytes

Outputs the sequence indefinitely.

1.step{|n|(2..$.|=n).one?{|x|$.%n%x<1}&&p(n)}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 9 (or 8?) bytes

[NbT‡Cp–

Outputs with newline delimiter.

Try it online.

If outputting as an infinite list is allowed it could be 1 byte less:

∞ʒbT‡Cp

Try it online.

Explanation:

[          # Start an infinite loop:
 N         #  Push the 0-based loop-index
  b        #  Convert it to a binary string
   T       #  Push 10
    Â      #  Bifurcate it; short for Duplicate & Reverse copy
     ‡     #  Transliterate the 1s to 0s and vice versa in the binary string
      C    #  Convert it back from a binary string to an integer
       p   #  Check if this integer is a prime number
        –  #  If it is: Print the loop-index `N` with trailing newline

∞          # Push an infinite positive list
 ʒ         # Filter it by:
  bT‡Cp   #  Same as above
           # (after which the resulting list is output implicitly)

bT‡C could alternatively be 2в_2β for the same byte-count in both programs: try it online.

  2в       #  Convert the integer to a base-2 list
    _      #  Check for each if it's equal to 0: 1 if 0; 0 otherwise
     2β    #  Convert it from a base-2 list back to an integer
\$\endgroup\$
2
\$\begingroup\$

Jelly, 6 bytes

BCḄẒƲ#

Try it online!

Takes an input n from STDIN and outputs the first n Gobar numbers. If we have to output all Gobar numbers, the following works for 9 bytes

ṄBCḄẒƲ¡‘ß

Try it online!

\$\endgroup\$
2
\$\begingroup\$

MathGolf, 10 bytes

òî_â┌ä¶╛p∟

Try it online.

Explanation:

ò        ∟  # Do while true without popping,
ò           # using the following eight characters as inner code-block:
 î          #  Push the 1-based loop-index
  _         #  Duplicate it
   â        #  Pop and convert it to a binary-list
    ┌       #  Invert each boolean
     ä      #  Convert it from a binary-list back to an integer
      ¶     #  Check if it's a prime number
       ╛    #  If it is:
        p   #   Pop and print the 1-based loop-index with trailing newline
\$\endgroup\$
2
\$\begingroup\$

R, 81 73 bytes

-8 bytes thanks to @Giuseppe.

while(T<-T+1)(k=(p=2^(0:log2(T)))%*%!T%/%p%%2)<2|sum(!k%%1:k)>2||print(T)

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ 75 bytes \$\endgroup\$
    – Giuseppe
    Commented Oct 22, 2021 at 17:37
  • 1
    \$\begingroup\$ in-lining the declarations for p and k gives 73 bytes by removing those pesky {}! \$\endgroup\$
    – Giuseppe
    Commented Oct 22, 2021 at 17:37
  • \$\begingroup\$ @Giuseppe, nice golfs, thanks! I don't know how I missed the dot product trick... \$\endgroup\$
    – pajonk
    Commented Oct 22, 2021 at 18:07
2
\$\begingroup\$

Vyxal, 7 bytes

λb†Bæ;ȯ

Try it Online!

Takes a number n and returns the first n numbers.

λ    ;ȯ # First n numbers where...
 b      # Binary
  †     # Vectorised logical not (Vyxal uses 1/0 for booleans)
   B    # When converted back to a number
    æ   # Is prime?
\$\endgroup\$
2
\$\begingroup\$

Python 3, 77, 70(@ovs), 65, 64 bytes

*p,x,z,P=5*[1]
while[p[z^x]or print(x)]:P*=x;x+=1;p+=-~P%x,;z|=x

Try it online!

Old version

Old version

Old version

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can save a few bytes by using Wilson's theorem for the primality test: TIO \$\endgroup\$
    – ovs
    Commented Oct 24, 2021 at 8:53
  • \$\begingroup\$ Thanks, @ovs. Neat trick. I managed to squeeze out another 5 bytes on top of that by losing the square and changing the prime store to (inverted) indicator list. \$\endgroup\$
    – loopy walt
    Commented Oct 24, 2021 at 11:00
1
\$\begingroup\$

JavaScript (V8), 75 bytes

Prints the sequence "forever" (i.e. until call stack overflow).

for(k=0;f=d=>x%--d?f(d):x>1&d<2;)f(x=++k^~-(1<<32-Math.clz32(k)))&&print(k)

Try it online!

Or  77  76 bytes without Math.clz32():

for(k=0;f=d=>x%--d?f(d):x>1&d<2;)f(x=++k^(g=k=>k&&1|2*g(k>>1))(k))&&print(k)

Try it online!

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

Pari/GP, 50 bytes

for(i=1,oo,if(isprime(2^#binary(i)-i-1),print(i)))

Try it online!

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

Charcoal, 38 bytes

Nθ≔¹ηW‹ⅉθ«≦⊕η≔↨E↨粬κ²ζ¿∧‹¹ζ⬤…²ζ﹪ζκ⟦Iη

Try it online! Link is to verbose version of code. Outputs the first n Gobar primes. Explanation:

Nθ

Input n.

≔¹η

Start at 1 (arbitrary, just has to be between 0 and 3 inclusive).

W‹ⅉθ«

Repeat until n Gobar primes have been printed.

≦⊕η

Try the next integer.

≔↨E↨粬κ²ζ

Convert it to base 2, flip the bits, then convert back.

¿∧‹¹ζ⬤…²ζ﹪ζκ

If the result is at least 2 and has no nontrivial proper factors, then...

⟦Iη

Print the Gobar prime on its own line.

The above algorithm appears to be O(n²) in complexity, taking 20 seconds to calculate the first 1400 Gobar primes and probably 20 minutes to calculate the first 7708. I've implemented a faster algorithm for 66 56 bytes that can calculate the first 7708 Gobar primes in 20 seconds (although it does start to slow down after that point due to using a memory-inefficient method of generating primes):

Nθ≔²η≔υζW‹Lυθ«≔Φζ‹×κκ⊗ηε≔⁺Φ⮌…η⊗η⬤ε﹪κμζζ≦⊗η≔⁺υ⁻⊖⊗ηζυ»I…υθ

Try it online! Link is to verbose version of code. Outputs the first n Gobar primes, although it actually works by calculating the primes up to the next power of 2. Explanation:

Nθ

Input n.

≔²η≔υζ

Start with the primes up to (but not including) 2, i.e. no primes at all.

W‹Lυθ«

Repeat until enough Gobar primes have been obtained.

≔Φζ‹×κκ⊗ηε

Get the primes up to the square root of the next power of 2.

≔⁺Φ⮌…η⊗η⬤ε﹪κμζζ

Calculate all the primes between the current and next power of 2 by trial division by all of those primes. (Sieving them would probably be even faster.)

≦⊗η

Double the current power of 2.

≔⁺υ⁻⊖⊗ηζυ

Complement the bits in all of the primes up to the current power of 2 with respect to that number of bits e.g. primes up to 4 have three bits complemented resulting in 4, 5 while primes up to 128 would have eight bits complemented. (Note that the list of primes is in reverse order so the complements are in ascending order as desired.)

»I…υθ

Output the first n Gobar primes.

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

Python 3.8 (pre-release), 106 bytes

n=1
while 1:(k:=int(bin((n^~-2**~-len(bin(n))))[3:],2))>1and all(k%m for m in range(2,k))and print(n);n+=1

Try it online!

Infinite output

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

Ruby, 71 70 bytes

require'prime'
1.step{|n|n.to_s(2).tr('01','10').to_i(2).prime?&&p(n)}

Try it online!

  • Saved 1 thanks to @ovs

Full program, prints the sequence indefinitely on new lines.

1.step{|n|     # each n>0
n.to_s(2)      # convert to binary string  
.tr('01','10') # swap '01'
.to_i(2)       # reconvert to int
.prime?&&p(n)  # put n if prime
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 70 bytes with && instead of if. \$\endgroup\$
    – ovs
    Commented Oct 23, 2021 at 19:00
  • \$\begingroup\$ This is a much shorter way to reverse the bits. \$\endgroup\$ Commented Oct 24, 2021 at 0:18
  • 3
    \$\begingroup\$ Actually, it seems shorter to do the primality test by hand. \$\endgroup\$ Commented Oct 24, 2021 at 0:49
  • \$\begingroup\$ @dingledooper wow that's a lot of improvements! Shouldn't you post your answer? It is not a completely different approach but still much different than mine \$\endgroup\$
    – AZTECCO
    Commented Oct 24, 2021 at 9:19
  • 1
    \$\begingroup\$ I sort of didn't want to post another one, but sure why not? \$\endgroup\$ Commented Oct 24, 2021 at 20:36

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.