Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
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.
5, 6 bytes∞'b⌐Bæ
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?
5, 8 bytes∞ƛb⌐Bæß,
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)
5 in the header if you're just using it to keep it from infinitely looping
\$\endgroup\$
Oct 22, 2021 at 16:40
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;}
Returns the zero-based \$n^\text{th}\$ Gobar prime.
[NbT‡Cp–
Outputs with newline delimiter.
If outputting as an infinite list is allowed it could be 1 byte less:
∞ʒbT‡Cp
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
BCḄẒƲ#
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ḄẒƲ¡‘ß
òî_â┌ä¶╛p∟
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
λb†Bæ;ȯ
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?
*p,x,z,P=5*[1]
while[p[z^x]or print(x)]:P*=x;x+=1;p+=-~P%x,;z|=x
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)
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! Link is to verbose version of code. Outputs the first n Gobar primes. Explanation:
Ｎθ
Input n.
≔¹η
Start at 1 (arbitrary, just has to be between 0 and 3 inclusive).
Ｗ‹ⅉθ«
Repeat until n Gobar primes have been printed.
≦⊕η
Try the next integer.
≔↨Ｅ↨粬κ²ζ
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...
⟦Ｉη
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):
Ｎθ≔²η≔υζＷ‹Ｌυθ«≔Φζ‹×κκ⊗ηε≔⁺Φ⮌…η⊗η⬤ε﹪κμζζ≦⊗η≔⁺υ⁻⊖⊗ηζυ»Ｉ…υθ
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:
Ｎθ
Input n.
≔²η≔υζ
Start with the primes up to (but not including) 2, i.e. no primes at all.
Ｗ‹Ｌυθ«
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.)
»Ｉ…υθ
Output the first n Gobar primes.
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
Infinite output
require'prime'
1.step{|n|n.to_s(2).tr('01','10').to_i(2).prime?&&p(n)}
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
