# Satan-Primes

who are they?
they are Primes containing 666
these are Satan-Primes:[46663,266677,666599,666683,616669]
these are NOT :[462667,665669,36363631,555]

# Plot

Every number bigger than 6661 has Satan-Primes behind him

# The Challenge

Given an integer n>6661 find the Satan-Prime behind (or equal) and closest to itself.

# Examples

Integer n=30000 has 3 Satan-Primes(SP) behind it:[6661, 16661, 26669].
Your code must return 26669 which is the closest behind it

# Test Cases

Input->Output

6662->6661
10000->6661
66697->66697 (a SP returns himself)
328765->326663
678987->676661
969696->966677


# Rules

Yor code should work for any n in the range of your language.

This is , so the shortest answer in bytes wins!

• define "about a minute." Is it +- 30 seconds? I personally think that 30 minutes and a minute don't differ that much... Also bonuses are generally frowned upon... also I think this might have been better as an output the nth satan prime challenge... Aug 25, 2017 at 16:47
• ok ok people... bonus will be removed...
– user73398
Aug 25, 2017 at 16:51
• Hope you don't mind the edit I made to the challenge title. Aug 25, 2017 at 17:29
• @Shaggy What point does the title change serve...? Aug 26, 2017 at 1:40
• @ConorO'Brien Rhyming and appearing archaic, I presume. Aug 26, 2017 at 15:17

# Neim, 9 bytes

>ͻ:D+6S𝕚÷


Explanation:

>         Increment input
ͻ        Start infinite loop
:        Previous prime
D       Duplicate
+6     Push 666
S    Swap
𝕚   See if 666 is a substring of the top of the stack
÷  If true, break


Try it online!

• So there's really a builtin to push "66 prepended to a digit"? O_O Neim has progressed. Aug 25, 2017 at 19:10
• How does +6 push 666? Or is Neim just that metal? Aug 26, 2017 at 5:58
• @RobertFraser Apparently +x means 612 + character code of x. The code of 6 happens to be 54, so 612+54=666. Aug 26, 2017 at 8:19
• @EriktheOutgolfer Well, Neim can represent all three digits numbers and a few four digits using two bytes.
– Okx
Aug 26, 2017 at 12:32
• @EriktheOutgolfer '\+* = 100,356,612,868 (plus the ordinal of the following char that is) Aug 26, 2017 at 13:13

# Mathematica, 82 bytes

Last@Select[Prime@Range@PrimePi@#,!FreeQ[Subsequences[IntegerDigits@#],{6,6,6}]&]&

• Wait, you mean there isn't a built-in for this one?
– anon
Aug 27, 2017 at 16:38

# Jelly, 10 9 bytes

Saved 10% thanks to @Dennis!

ÆRwÐf666Ṫ


Try it online!

### Explanation

ÆR          # All primes in range [2, input]
Ðf      # Keep those which satisfy
w        # truthy if y is in x
666   #           ^ (this is y)
Ṫ  # Tail (take the last element)

• Alternative: ÆRẇ@Ðf666Ṁ Aug 25, 2017 at 17:30
• I love that the Tail (right after 666) looks like a cross. Aug 25, 2017 at 20:11
• w should work instead of ẇ@. Aug 26, 2017 at 3:21
• @Dennis s/sh/w/ of course it works :p Aug 26, 2017 at 13:17

# Pyth, 15 14 bytes

Saved 1 byte with help from Dave.

Memory errors for 969696 and anything higher on my machine, but it is fine if it is given enough memory.

ef&/T*3\6P_TS


Try it here or check out the Test Suite.

# How?

ef&/T*3\6P_TSQ - Full program, with implicit input (Q) at the end

SQ - Range [1,Q]
f              - Filter.
P_T   - Is prime?
&             - And
/T*3\6      - It contains 666.
e               - Last element.
- Implicitly output the result.


# Pyth, 14 bytes

ef/T*\63fP_TS


Try it here!

• 14 bytes: ef&/T*3\6P_TS
– Dave
Aug 25, 2017 at 17:10
• I added the ending Q by mistake, its 14
– Dave
Aug 25, 2017 at 17:10
• "666" is a less efficient way to describe the string 666 that *3\6
– Dave
Aug 25, 2017 at 17:11

# 05AB1E, 11 bytes

ƒNpN666å*iN


Try it online!

# Bash + Core Utils, 51 49 Bytes

seq $1|tac|factor|awk 'NF==2&&/666/&&!a--&&$0=$2'  Takes command line argument. Can be quite slow with larger numbers. • This outputs all "satan primes" down to 6661, but it should only be printing the closest one below the input: try it online. One fix would be to just add |head -1 to the end. Aug 26, 2017 at 2:47 • @JustinMariner lol, whoops, fixed it Aug 26, 2017 at 4:25 # Mathematica, 646261 53 bytes #//.i_/;!PrimeQ@i||ToString@i~StringFreeQ~"666":>i-1&  -1 byte thanks to @KellyLowder -8 bytes (wow) thanks to @Notatree ## Explanation Take an input. We decrement it under these conditions: • the input is not prime, OR • the digits of the inputs does not contain three 6s in a row. We repeat that until a Satan prime is reached. • Very nice. You can lose one more _ at the end since a prime can't end in 6. Aug 25, 2017 at 20:33 • @KellyLowder good point Aug 26, 2017 at 4:13 • This is even shorter with strings: #//.i_/;!PrimeQ@i||ToString@i~StringFreeQ~"666":>i-1& Aug 26, 2017 at 5:44 • @Notatree wow! nice! Aug 26, 2017 at 15:05 # Perl 5, 47 bytes 46 bytes of code + 1 for -p {$f=0|sqrt;1while$_%$f--;/666/*!$f||$_--*redo}


Try it online!

# Japt, 14 bytes

õ fj w æ_sø666


Test it

Seeing as there was a 50% time-based bonus: Completes test case 969696 in under half a second.

## Explanation

Implicit input of integer U.

õ


Generate an array of integers from 1 to U.

fj


Filter (f) primes.

w


Reverse.

æ_


Return the first element that returns a truthy value (in this case 1) when passed through a function that checks if ...

sø666


The integer converted to a string (s) contains (ø) 666.

## Faster Alternative, 15 bytes

Again, seeing as there was originally a time-based bonus, here's an alternative, and much faster, solution which I can't seem to golf any further.

U-@j *U´sø666}a


Test it

# PowerShell, 128 bytes

param($n)function f($a){for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}}}for(){if($n-match666-and($n-eq(f $n))){$n;exit}$n--}  Try it online! PowerShell doesn't have any prime factorization built-ins, so this borrows code from my answer on Prime Factors Buddies. We take input $n, then declare a new function f that calculates out the factors of input $a. If the input $a is prime, then this will return just $a. The main part of the program is the infinite for() loop. Inside the loop, we check if $n -matches against 666 and whether $n is prime (i.e., $n matches all of the factors of $n). If it is, we place $n on the pipeline and exit, with implicit output. Otherwise, we decrement $n-- and continue the loop. # Python 2, 77 76 bytes Edit: -1 byte thanks to @Mr.Xcoder Slow running time, runs in O(n^2) lambda x:max(q for q in range(x+1)if"666"inq*all(q%t for t in range(2,q)))  Try it online! ## Another 76 bytes solution lambda x:max(q*("666"inq*all(q%t for t in range(2,q)))for q in range(x+1))  Try it online! # With SymPy 73 bytes lambda x:max(q for q in primerange(0,x+1)if"666"inq) from sympy import*  Try it online! • 76 bytes: lambda x:max(q for q in range(x+1)if"666"inq*all(q%t for t in range(2,q))) - use max() instead of [][-1] Aug 25, 2017 at 17:18 # PowerShell, 7169 64 bytes param($s)for(;$s-notmatch666-or(2..($s/2)|?{!($s%$_)});$s--){}$s


Try it online!

• 328765 takes ~30 seconds on my machine, but times out the 60 second limit on Tio.run.

• 678987 takes ~1.5 minutes.

• 969696 takes ~4.5 minutes.
• Clever way of doing the factors. Aug 29, 2017 at 12:33

# C++ 389 bytes

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
using namespace boost::random;typedef boost::multiprecision::cpp_int Z;int main(int,char**v){mt19937 m(clock());independent_bits_engine<mt11213b,256,Z>g(m);Z n{v[1]},p;while(p++<=n)if(miller_rabin_test(p,25,g)&&p.convert_to<std::string>().find( "666" )!=-1)std::cout<<p<<" ";}


This is a full program!
You'll need Boost to compile it. (Or copy and paste into your favorite online C++ shell.)
Run it from the command-line giving n as argument.

Ungolfed:

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
using namespace boost::random;

typedef boost::multiprecision::cpp_int integer;

int main( int argc, char** argv )
{
mt19937 mt( clock() );
independent_bits_engine <mt11213b, 256, integer> rng( mt );

integer input {argv[ 1 ]};
integer possible;

while (possible++ <= input)
if (
// is_prime( possible )
miller_rabin_test( possible, 25, rng )
&&
// possible has "666" in it
(possible.convert_to <std::string> ().find( "666" ) != std::string::npos))

std::cout << possible << " ";
}


Shortcuts were made in terms of random number testing. The original code started testing possible primes at 6661 and incremented by two. You'll also get a compiler warning because of that (-1) there instead of npos.

Still, this runs pretty quickly. It only took about 40 seconds to find all 214 satan primes under 1,000,000 on my old AMD Sempron 130.

:^D

# Bash + bsd-games package, 33

• 2 bytes saved thanks to @FedericoPoloni.
primes 2 $[$1+1]|grep 666|tail -1

• You can save 1 byte if you replace the last two commands with tail -n1. Aug 26, 2017 at 8:10
• @FedericoPoloni duh - can't believe I forgot tail here. In fact tail -1 is even 1 less. Aug 30, 2017 at 16:56

# Stax, 10 bytes

ü>:Ñb/VP6─


Run and debug it

Explanation (unpacked):

^w:pc$666$#! Full program, implicit input-parsing
^            Increment input
w           do-while:
:p           Previous prime
c$Copy and stringify 666$     Push "666"
#    Number of occurences
!   Logical not
Implicit output

• Nice program. Thanks for trying stax. FYI, it's also possible to do multiple cases by using the "Separator" option like this May 1, 2018 at 14:09
• @recursive ah, thx May 1, 2018 at 14:48

# R, 57 bytes

(a=conf.design::primes(scan():1))[which(grepl(666,a))[1]]


-42 bytes from Dominic Van Essen's enormous golf.

uses grepl to coerce values to string(since 666 cannot be considered a regex) and check for truthy values.

Runs through the array in reverse to save 2 bytes.

# R + conf.design, 81 78 99 bytes

library(conf.design);function(n){a=primes(1:n)
a[max(which(grepl("666",as.character(a),fixed=T)))]}


Try it on rdrr.io!

My first R solution.

+21 bytes after including library name.

A simple filter. grepl returns true at indices with 666, which returns the truthy indices, and max gets the required index of the prime.

• Congratulations on your first R golf! The good news: you can make the code shorter (58 bytes) like this function(n)(a=primes(1:n))[max(which(grepl("666",a,f=T)))], and then even shorter (52 bytes) by using scan() for input like this (a=primes(1:scan()))[max(which(grepl("666",a,f=T)))] (but I don't know how to make scan() work correctly on rdrr.io... Sep 22, 2020 at 7:25
• The bad news is that the current consensus (that I only recently learned of) is that we need to include either the code to load the library (library(conf.design)) or to specify the library for the function (conf.design::primes) in the byte-count, which brings the shortest version back up to 65 bytes: (a=conf.design::primes(1:scan()))[max(which(grepl("666",a,f=T)))]. Sep 22, 2020 at 7:31
• Actually, 57 bytes: (a=conf.design::primes(scan():1))[which(grepl(666,a))[1]], by letting grepl coerce both arguments to character, leaving-out the fixed=TRUE which isn't required here (because 666 can't be mistaken for a regex), and running-through the series in reverse order, so we can take the first ([1]) element instead of the max(). Sep 22, 2020 at 7:43
• I've edited the answer to include the right solution. Sep 22, 2020 at 7:45
• 56 bytes using match(T,x) (that always returns the first matching element) instead of which(x)[1]: (a=conf.design::primes(scan():1))[match(T,grepl(666,a))] Sep 22, 2020 at 14:27

# MATL, 16 bytes

ZqP"@V'666'Xf?@.


Try it at MATL Online

Explanation

         Implicitly grab input (n)
Zq       Compute the primes up to n (output is in increasing order)
P        Flip the array (so larger primes come first)
"        For each prime
@V     Convert it to a string
'666'  Push the string literal '666' to the stack
Xf     Find the location of '666' in the prime
?      If it was present...
@.   Push it to the stack and break
Implicitly display the stack contents


# Python 3, 85 83 80 bytes

Halvard's is 4 bytes shorter because it's done in Python 2.

lambda k:max(x for x in range(k+1)if"666"in str(x)*all(x%i for i in range(2,x)))


Try it online!

Give it some time, it's extremely slow because of its O(n^2) complexity.

# JavaScript (ES6), 55 54 bytes

-1 byte thanks to @ThePirateBay.

f=n=>/666/.test(d=n)&eval("while(n%--d);d<2")?n:f(n-1)


Very slow with large inputs. Primality test adapted from this code golf answer.

## Timings

• Input 10000 took 10 seconds
• Input 328765 took 3 minutes
• Input 678987 took 9 minutes
• Input 969696 took 16 minutes

## Tests

Some of these will hang your browser for several minutes.

f=n=>/666/.test(d=n)&eval("while(n%--d);d<2")?n:f(n-1)

function test(n) {
O.value="Working..."
setTimeout(_=>{
let t = Date.now()
O.value=f(${n}) =${f(n)} in ${(Date.now()-t)/1000}s }, 10) } Tests<br> <button onclick="test(6662)">6662</button> <button onclick="test(10000)">10000</button> <button onclick="test(328765)">328765</button> <button onclick="test(678987)">678987</button> <button onclick="test(969696)">6662</button><br> Result<br> <input id=O type=text size=25 readonly> ## Faster Version, 56 bytes Completes each test case in under a second. f=n=>/666/.test(n)&&eval("for(d=2;n%d++;);d>n")?n:f(n-1) ;[6662, 10000, 328765, 678987, 969696].forEach(n=>console.log(f(${n}) -> ${f(n)})) • You should never do that. This is code golf and the performance is totally irrelevant. I strongly suggest rolling back to your previous 55 byte answer. Also, you can reduce it to 54 bytes by replacing d==1 with d<2 since n>6661. – user72349 Aug 26, 2017 at 5:41 • 52 bytes: f=n=>/666/.test(n)&(g=d=>n%--d?g(d):d<2)(n)?n:f(n-1) but will throw a recursion error for larger numbers. Aug 30, 2017 at 16:45 # Ruby, 67, 66, 58, 56 bytes Includes +7 bytes for -rprime ->z{z.downto(1).find{|x|/666/=~x.to_s&&x.prime?}}  It's pretty fast, computing values up to ~2^52 in about a second and 2^64 in under 5 minutes (2011 MBP, Ruby 2.3.1). # PHP, 148 bytes <?php$p=[2];$s=[];for($i=3;$i<=$argv[1];$i++){foreach($p as $q)if($i%$q===0)continue 2;$p[]=$i;if(strpos($i,'666')!==false)$s[]=$i;}echo end($s);?>  Try it online! # Perl 6, 35 bytes my&f={/666/&&.is-prime??$_!!f $_-1}  Try it online! Straightforward recursive solution. # C# (.NET Core), 117115 112 bytes f=>{for(int i=f;i>1;i--){int p=1,j=2;while(j<i)if(i%j++<1)p=0;if(p>0&$"{i}".Contains("666"))return i;}return 0;}


Try it online!

• 2 bytes saved by removing unnecessary braces.
• 3 bytes saved by combining int declarations.

I'm sure this could be made shorter; maybe by recursively calling func f and removing the outer for-loop.

### Recursive Approach, 85 bytes

i=>{int p=1,j=2;while(j<i)if(i%j++<1)p=0;return p>0&\$"{i}".Contains("666")?i:f(--i);}


Try it online!

I'm unsure how well this approach fits within the bounds of code-golf due to having to set the Func<int,int> f = null first, and that f is called again, but not counted towards the bytes. Any clarification would be appreciated.

# 05AB1E, 9 bytes

ÅPR.Δ666å


Try it online. (No test suite with all test cases, because it's a bit too slow.)

Explanation:

ÅP         # Push a list of primes below or equal to the (implicit) input-integer
R        # Reverse this list
.Δ      # Find the first value which is truthy for:
666å  #  Check whether it contains "666" as substring
# (after which the found result is output implicitly)


The 666 can alternatively be Ž2ć (compressed 666) or Ƶé· (compressed 333 and then doubled).

# Java 8, 77 bytes

n->{for(int i=++n;i>1|!(n+"").contains("666");)for(i=--n;n%--i>0;);return n;}


Try it online.

Explanation:

n->{               // Method with integer as both parameter and return-type
for(int i=++n;   //  Increase the input by 1
//  Set i to this input+1 (setting i to anything above 1 is fine)
i>1          //  Continue looping as long as i is not 0 nor 1
|!(n+"").contains("666");)
//  or if n as String does not contain "666" as substring:
for(i=--n;     //   Decrease n by 1 first
//   And then set i to this new n
n%--i      //   Decrease i by 1 before every iteration
>0;); //   And continue looping as long as n does NOT evenly divide i
return n;}       //  After both loops, return the modified n as result


If for(i=n;n%--i>0;); results in $$\i<2\$$, it means $$\n\$$ is a prime number (note: this prime checker only works for $$\n\geq2\$$, which is fine in this case).

# Husk, 12 bytes

ḟo€d666dfṗṫ


Try it online!