12
\$\begingroup\$

A Belphegor number is a number of the form \$(10^{n+3}+666)*10^{n+1}+1\$ (1{n zeroes}666{n zeroes}1) where \$n\$ is an non-negative integer. A Belphegor prime is a Belphegor number that is also prime.

The \$n\$ values of the first few Belphegor primes are 0, 13, 42, 506 (A232448)

Task

Write a program that either:

  • takes no input and outputs all Belphegor primes.
  • takes a input \$k\$ and outputs the first \$k\$ Belphegor primes.

A reference python implementation can be found here.

Rules

  • You may output the \$n\$ value for the Belphegor prime instead of the prime itself
  • You may use probabilistic primality tests as long as there is no known counter case.

Scoring

This is so shortest bytes wins.


Inspired by The Most Evil Number - Numberphile

\$\endgroup\$
  • 2
    \$\begingroup\$ what do you mean by "All"? there might be infinitely many... \$\endgroup\$ – J42161217 May 27 at 16:33
  • \$\begingroup\$ @J42161217 by "All" I mean to write an program that does not stop and will eventually output all Belphegor primes. \$\endgroup\$ – Mukundan314 May 27 at 16:37
  • \$\begingroup\$ Do you mean "\$n\text{-th}\$ value" by "\$n\$ value"? \$\endgroup\$ – Jonathan Frech May 27 at 22:48
  • 2
    \$\begingroup\$ To be pedantic (and reading the fine print), the only known Belphegor primes are 16661 and 1000000000000066600000000000001. The rest of the numbers in the sequence are only probable primes. \$\endgroup\$ – Abigail May 28 at 10:48
  • 1
    \$\begingroup\$ I find the criterion as long as there is no known counter case a bit shaky. It sounds like "it's fine as long as we can't tell". (For example, even if we don't know a counter case for a strong Baillie-PSW primality test to date, it is conjectured that there are infinitely many of them.) \$\endgroup\$ – Arnauld May 29 at 8:06

10 Answers 10

4
\$\begingroup\$

Wolfram Language (Mathematica), 51 bytes

outputs the n value
"...program that does not stop and will eventually output all..."

PrimeQ[10^c*666+1+100^++c]~If~Print[c-2]~Do~{c,∞}     

Try it online!

thanks to @DanTheMan for saving 4 bytes
and also to @mypronoun -7 bytes

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Using Do[...,∞] would be shorter than using While. Additionally, If can use infix syntax. \$\endgroup\$ – DanTheMan May 28 at 0:32
  • \$\begingroup\$ 53 bytes: Try it online! \$\endgroup\$ – the default. May 28 at 5:30
  • 1
    \$\begingroup\$ 51 bytes by rearranging 10^(2c+2) to 100^++c: Try it online! \$\endgroup\$ – the default. May 28 at 10:53
  • \$\begingroup\$ @mypronounismonicareinstate good job! \$\endgroup\$ – J42161217 May 28 at 13:26
3
\$\begingroup\$

Pyth, 17 bytes

.fP_sj666_B`^TZQ0

Try it online!

Takes k as input and outputs the n corresponding to the first k Belphegor primes.

Explanation:

.fP_sj666_B`^TZQ0
.f             Q0    Find the first k values of Z where the following is true,
                     starting at 0 and counting upwards.
            ^TZ      Raise 10 to the power of Z
           `         Convert to a string
         _B          Pair with reversal
     j666            Join with 666 in the middle
    s                Convert to number
  P_                 Check for primality.
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 14 bytes

∞<ε0Xr×66Jû}ʒp

Outputs the infinite sequence.
Extremely slow due to the prime-check on large numbers, so times out before it even reaches the n=13 Belphegor prime on TIO..

Try it online or verify the numbers without the prime-check filter.

Explanation:

∞             # Push an infinite positive list: [1,2,3,...]
 <            # Decrease each by one to make it start at 0: [0,1,2,...]
  ε           # Map each value to:
   0          #  Push a 0
    X         #  Push a 1
     r        #  Reverse the stack order: [value, 0, 1] to [1, 0, value]
      ×       #  Repeat the 0 the value amount of times as string
       66     #  Push 66
         J    #  Join the values on the stack together: "10...066"
          û   #  Palindromize it: "10...06660...01"
  }ʒ          # After the map: filter the list by:
    p         #  Check whether it's a prime number
              # (after which the resulting list is output implicitly)
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Ruby -rprime, 45 bytes

Prime.map{|p|p p if"#{p}"=~/^1(0*)666(\1)1$/}

Try it online!

Stutters, then checks all primes against a Belphegor prime regex. Very slow.

(Edit: Kudos to @Abigail, whose earlier Perl answer used a similar regex. I didn't notice it until after I posted my answer.)

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

Jelly, 19 bytes

+ؽṬ6×1;ŒḄḌṄẒ¡×0µ1#

A full program which prints the Belphegor primes.

Try it online!

How?

+ؽṬ6×1;ŒḄḌṄẒ¡×0µ1# - Main Link: no arguments (implicit input = 0)
                µ1# - count up, from n = 0, finding the first n for which
                      this yields a truthy value:
 ؽ                 -   [1,2]
+                   -   add to n -> [n+1, n+2]
   Ṭ                -   un-truth -> [0]*n+[1,1]  (e.g. n = 3: [0,0,0,1,1])
    6×              -   multiply by six -> [0]*n+[6,6]
      1;            -   prefix with a one -> [1]+[0]*n+[6,6]
        ŒḄ          -   bounce -> [1]+[0]*n+[6,6,6]+[0*n]+[1]
          Ḍ         -   from base 10 -> 100...0066600...001
             ¡      -   repeat...
            Ẓ       -   ...number of times?: is prime?
           Ṅ        -   ...action?: print it and a newline character
              ×0    -   multiply the result by 0 (forcing an infinite loop)
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Python 3, 80 bytes

b=2
while 1:n=100**b+10**~-b*666+1;all(n%m for m in range(2,n))and print(n);b+=1

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ By "you may use probabilistic primality tests as long as there is no known counter case." i meant any counter case not just counter cases that are belphegor primes. And fermat primality tests with base 2 has lot of counter cases oeis.org/A001567 \$\endgroup\$ – Mukundan314 May 28 at 3:31
  • \$\begingroup\$ @Mukadan I see. So what kind of probabilistic primality test doesn't have a known counter case? \$\endgroup\$ – dingledooper May 28 at 3:47
  • \$\begingroup\$ Baillie–PSW primality test or miller-rabin with the bases 2, 325, 9375, 28178, 450775, 9780504, 1795265022. Both of them are deterministic upto 2^64 and have no known counter cases \$\endgroup\$ – Mukundan314 May 28 at 3:56
  • \$\begingroup\$ 79 bytes with Wilson‘s Theorem, outputs n. \$\endgroup\$ – ovs May 28 at 6:50
  • \$\begingroup\$ 77 bytes, because 4 is (obviously) not a Belphegor number. \$\endgroup\$ – ovs May 28 at 8:42
2
\$\begingroup\$

perl -M5.010 -Mbigint -Mexperimental=signatures, 62 70 bytes

sub p($m=3){$m>=$_||($_%$m&&p($m+2))}$_=16661;{p&&say;s/6+/0$&0/;redo}

Try it online!

@ikegami pointed out the original solution doesn't work, because .. doesn't work well with bigints. So we replaced it with recursive function which checks whether a number is a prime (by checking whether it isn't evenly divisible by any odd digit less than the tested number (excecpt 1)). We also no longer iterating over all numbers, instead, we're just checking all the Belphegor numbers; we can easily make the next one from the previous by replacing 666 by 06660.

It's still slow, because of the rather dumb primeness checking. Running it on TIO doesn't actually produce any output (it seems to run at most one minute). Running it from the command line quickly produces 16661, but I couldn't bother waiting for it to reach 1000000000000066600000000000001, the next Belphegor prime. It is likely to die from memory exhaustion when trying to determine one of the Belphegor numbers is prime, before finding 1000000000000066600000000000001 anyway.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This doesn't work. .. requires native ints, so your bigints are being converted to native ints. Your program will die with Range iterator outside integer range long before finding 1000000000000066600000000000001. (Try perl -Mbigint -e'$x = 1000000000000066600000000000001; grep 1, 2..$x-2'.) \$\endgroup\$ – ikegami May 28 at 8:18
1
\$\begingroup\$

Pyth, 22 bytes

.V0IP_h*+^T+3b666^Thbb

Try it online!

Implements the formula provided in the question. Prints the n values rather than the primes themselves.

Since this version (not surprisingly) times out on TIO, here is a version that prints all n values lower than the input: Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Alternate 22 byte solution by doing string addition \$\endgroup\$ – Mukundan314 May 28 at 3:17
1
\$\begingroup\$

JavaScript (Node.js), 71 bytes

A full program that prints Belphegor primes forever ... and takes forever to print them.

for(k=10n;;)for(d=n=666n*k+(k*=10n)*k+1n;n%--d||d<2n&&console.log(n););

Try it online!

Commented

for(k = 10n;;)            // outer loop: start with k = 10 and loop forever
  for(                    //   inner loop:
    d = n =               //     start with d = n =
      666n * k +          //       666 * k +
      (k *= 10n) * k +    //       (10 * k)² +
      1n;                 //       1
                          //     and update k to 10 * k
      n % --d ||          //     decrement d until it divides n
        d < 2n &&         //     if d is less than 2:
          console.log(n); //       n is prime --> print it
  );                      //

JavaScript (Node.js), 176 bytes (non-competing)

A much faster version that uses a single iteration of the Miller-Rabin primality test.

for(k=10n;;)(n=666n*k+(k*=10n)*k+1n,~-(x=(g=(d,r,a)=>d?g(d/2n,d&1n?r*a%n:r,a*a%n):r)(d=n/(~-n&1n-n),1n,2n))&&~x+n?(g=d=>~d+n?~-(x=x*x%n)?~x+n&&g(d+d):1:1)(d):0)||console.log(n)

Try it online!

I guess it doesn't comply with the challenge rules since the test is likely to produce false-positives. It does however find the same 5 first terms as other answers.

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

Python, 220 164 bytes

def a(k,s=set()):
 for i in range(k):
  p=1;n=(10**(i+3)+666)*10**-~i+1
  for d in range(1,int(n**.5//1/2)):
   p*=n%-~(d*2)>0
   if~-p:break
  s.add(p*n)
 return s

Simple prime search by checking modulus below the square root; fastened by skipping every even divisor.

Likely there's room for improvement, as it becomes incredibly slow for k > 10.


Edit: thanks to @JonathanAllan and @mathjunkie for ideas and sources. This update has heavy use of tweaks and bit-operations.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I doubt that altering the golfiest Python prime identifying program would even print out the first one without stupid amounts of resources :) \$\endgroup\$ – Jonathan Allan May 27 at 22:35
  • 1
    \$\begingroup\$ True->1; inline the ifs; use p*=n%((d*2)+1)>0 (maybe even p*=n%-~(d*2)>0?); (i+1)->-~i \$\endgroup\$ – Jonathan Allan May 27 at 22:38
  • 1
    \$\begingroup\$ from math import* appears to be shorter. \$\endgroup\$ – Jonathan Frech May 27 at 22:46
  • \$\begingroup\$ @JonathanAllan can you explain -~i? I'm not familiar with bitwise operators that much. How negating the bitwise negation of i equals +1? \$\endgroup\$ – Zoltán Schmidt May 27 at 23:33
  • 2
    \$\begingroup\$ @ZoltánSchmidt Take a look at this Python golfing tip \$\endgroup\$ – math junkie May 27 at 23:36

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.