29
\$\begingroup\$

As we all know, it's turtles all the way down. But is it primes all the way down too?

A number is considered a "turtle-prime" if it satisfies the following conditions:

1) It is prime. 2) It is possible to remove a single digit leaving a prime number. 3) Step 2 can be repeated until left with a single digit prime.

For example, 239 is a "turtle-prime", as it can be reduced to 23 then either 2 or 3, both of which are prime. It also can be reduced to 29 then 2. 151 is not a turtle prime, as it reduces to 15 (not prime), 51 (not prime), or 11. 11 is prime, but can only reduce to 1, which is not.

Given a positive integer, determine if it is a "turtle-prime". Your output can be in any form so long as it gives the same output for any truthy or falsey value.

Test cases:

input -> output 1 -> false 2 -> true 17 -> true 19 -> false 239 -> true 389 -> false

Scoring

This is , so the shortest answer in each language wins!

Improve this question
\$\endgroup\$
6
  • 5
    \$\begingroup\$ Related \$\endgroup\$ Commented Jul 17, 2017 at 16:55
  • \$\begingroup\$ @MagicOctopusUrn WOW \$\endgroup\$ Commented Jul 17, 2017 at 16:56
  • 9
    \$\begingroup\$ Actually related \$\endgroup\$ Commented Jul 17, 2017 at 16:56
  • 3
    \$\begingroup\$ Can we take input as a list of digits? \$\endgroup\$ Commented Jul 17, 2017 at 17:02
  • 2
    \$\begingroup\$ Your conditions say that all single-digit primes are not turtle primes. Condition 2 fails: it is not possible to remove a digit and still leave a prime number, as removing the only digit leaves nothing. \$\endgroup\$ Commented Jul 18, 2017 at 20:04

13 Answers 13

Reset to default
7
\$\begingroup\$

Haskell, 104 102 99 98 97 95 91 bytes

p x=product[2..x-1]^2`mod`x>0 f[]=1>0 f x|y<-zip[0..]x=or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

Try it online!

Explanation

First we set up a primality test

p x=product[2..x-1]^2`mod`x>0

This uses Wilson's Theorem to determine the primality of an input.

We then declare a base case, which will assert that the empty string is truthy.

f[]=1>0

Now we define the actual function

f x|y<-zip[0..]x=or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

We use a pattern guard to bind zip[0..]x to y, because we need to use it twice later. We then assert the answer is

or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

[[snd b|b<-y,b/=a]|a<-y] is all of the numbers that are a digit removed from our input. So we are asserting that at least one of these numbers is truthy for f. In order to ensure that composite numbers are falsy we add in prime$read x. If the number is not prime the list will become empty and the any of a empty list is false.

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ −2 bytes: any f[[ ↦ or[f[ \$\endgroup\$ Commented Jul 17, 2017 at 21:37
  • 1
    \$\begingroup\$ −4 bytes: [b|(i,b)<-y,i/=a]|(a,_)<-y ↦ [snd b|b<-y,b/=a]|a<-y \$\endgroup\$ Commented Jul 17, 2017 at 21:43
6
\$\begingroup\$

Jelly, 16 bytes

DŒPḊṖLÐṀḌ߀¬Ȧ<ÆP

Try it online!

How it works

DŒPḊṖLÐṀḌ߀¬Ȧ<ÆP Main link. Argument: n D Decimal; convert n to base 10. ŒP Powerset; get all sub-arrays of n's decimal digits. Ḋ Dequeue; remove the first sub-array (empty array). Ṗ Pop; remove the last sub-array (all of n's digits). LÐṀ Maximal by length; keep those of the remaining subarrays that have maximal length. This keep exactly those sub-arrays that have one (and only one) digit removed. If n < 10, this yields an empty array. Without Ḋ, it would yield [[]] instead. Ḍ Undecimal; turn the generated digit arrays into integers. ߀ Recursively map the main link over the generated integers. ¬ Negate; map 1 to 0 and 0 to 1. Ȧ Any and all; yield 0 if the array is empty (n < 10) or any of the recursive calls returned 1 (mapped to 0). If all calls returned 0, this will yield 1. ÆP Test n for primality, yielding 1 for primes, 0 otherwise. < Test if the result to the left is less than the result to the right. This is possible only if the left result is 0 (n < 10 or removing a digit results in a turtle prime) and the right result is 1 (n itself is prime).
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ More magic Jelly! Man, this stuff gets everywhere... \$\endgroup\$ Commented Jul 18, 2017 at 21:32
6
\$\begingroup\$

R, 124 122 120 113 95 93 106 105 bytes

 g=pryr::f(`if`(gmp::isprime(sum(x*10^((l<-sum(x|1)-1):0))),any(!l,sapply(0:l+1,function(z)g(x[-z]))),!1))

Which evaluates to the function:

function (x) if (gmp::isprime(sum(x * 10^((l <- sum(x | 1) - 1):0)))) any(!l, sapply(0:l + 1, function(z) g(x[-z]))) else !1

Recursive solution. Takes input as a list of digits.

Has 2 logical statements:

  1. Is x prime when concatenated?

  2. Is any of the following TRUE:

    1. Is the length of x nonzero? This is our final terminating condition.

    2. Is f TRUE for any subset of x?

The first statement ensures we keep working with primes only. The second does the actual recursion.

Saved two bytes thanks to @Giuseppe.

I had to revert some of my golfs because of a bug, where I was testing with a previous function definition by accident.

R, 98 bytes, non-competing

Like I mentioned in the comments, I made a package. Since the challenge predates that, this is non-competing, but I wanted to showcase it a bit. It's not much so far, but we'll get there.

g=pryr::f(`if`(gmp::isprime(RG::C(x)),any(!(l<-sum(x|1)-1),sapply(0:l+1,function(z)g(x[-z]))),!1))

C() is the first function in the package, and takes care of concatenating digits into a numeric.

Improve this answer
\$\endgroup\$
11
  • \$\begingroup\$ Some of these operations (Looking at you sum(x*10^(((l<-sum(x|1))-1):0))) are sooo damned wordy. I am really considering creating a golf package for R. \$\endgroup\$ Commented Jul 17, 2017 at 18:34
  • \$\begingroup\$ this would have been my solution but I couldn't wrap my head around the sapply... Also I think you may want to do f=pryr::f(...) or else you need to use f in the sapply. \$\endgroup\$ Commented Jul 17, 2017 at 19:07
  • 1
    \$\begingroup\$ @Giuseppe Single letter names for everything :D Why not call the package g or something? \$\endgroup\$ Commented Jul 17, 2017 at 19:58
  • 1
    \$\begingroup\$ @Giuseppe Created the start for a package :p Take a look: github.com/JarkoDubbeldam/RG \$\endgroup\$ Commented Jul 18, 2017 at 20:20
  • 1
    \$\begingroup\$ @JarkoDubbeldam beautiful. I'm sure future challenges will make obvious what additional functions need to be added. String manipulation is big: something for el(strsplit(x,'')) would save a ton of bytes. \$\endgroup\$ Commented Jul 18, 2017 at 20:59
5
\$\begingroup\$

Jelly, 19 bytes

DJḟЀ`ịDḌḟ0߀¬Ȧ¬aÆP

Try it online!

How it works

DJḟЀ`ịDḌḟ0߀¬Ȧ¬aÆP input:239 D decimal [2,3,9] J range@length [1,2,3] ḟЀ` filter out each [[2,3],[1,3],[1,2]] ịD index&decimal [[3,9],[2,9],[2,3]] Ḍ undecimal [39,29,23] ḟ0 filter out 0 [39,29,23] ߀ this@each [1,1,1] ¬ logical not [0,0,0] Ȧ any and all 0 ¬ logical not 1 aÆP and&is_prime 1

Recursion without base case ftw.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Jelly, 27 26 bytes

DµœcL’$Ḍµ€FÆPÐf ×⁵WÇÐĿFṪ<8

A monadic link taking and returning integers (1 for turtle 0 otherwise).

Try it online!

How?

DµœcL’$Ḍµ€FÆPÐf Link 1: primes by digit removal: list of numbers e.g. [19790] D cast to decimal list (vectorises) [[1,9,7,9,0]] µ µ€ monadic chain for €ach: $ last two links as a monad: L length 5 ’ decrement 4 œc combinations without replacement [[1,9,7,9],[1,9,7,0],[1,9,9,0],[1,7,9,0],[9,7,9,0]] Ḍ cast from decimal list (vectorises) [1979,1970,1990,1790,9790] F flatten (from a list of lists form the for €ach to a single list) Ðf filter keep if: ÆP is prime? ×⁵WÇÐĿFṪ<8 Main Link: number, n e.g. 1979 ⁵ literal 10 × multiply 19790 (this is so the first number is tested as prime too) W wrap in a list [19790] ÐĿ loop, collecting results (including the input×10) while change still occurs: Ç call the last (1) link as a monad [[19790],[1979],[197,199,179],[19,17,97,19,19,17,19,79],[7,7,7,7],[]] F flatten [19790,1979,197,199,179,19,17,97,19,19,17,19,79,7,7,7,7] Ṫ tail 7 <8 less than 8? 1 (if a single digit prime was reached this will be 1 otherwise it will be 0 e.g. an input of 4 yields 40 at the end which is not <8)
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ It's interesting seeing two substantially different Jelly answers. Lets see who can cut theirs down smaller. \$\endgroup\$ Commented Jul 17, 2017 at 18:00
2
\$\begingroup\$

Ruby, 72 57+8 = 80 65 bytes

Uses the -rprime flag. -15 bytes from histocrat!

f=->n{n==''||n.to_i.prime?&!n.scan(/./){f[$`+$']&&break}}

Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ You can replace &&!! with just &, it will cast the result to a boolean. Your recursive call can also get a little shorter using perlisms: !n.scan(/./){f[$`+$']&&break}} \$\endgroup\$ Commented Jul 17, 2017 at 20:52
  • \$\begingroup\$ @histocrat Ah yes, I forgot that I didn't actually need boolean short-circuiting for that last part due to the initial condition. Do you know why the n.scan trick works the way it does? \$\endgroup\$ Commented Jul 17, 2017 at 21:08
  • 1
    \$\begingroup\$ Yeah, the two global variables there are set to the string to the left and right of the most recent match, so concatenating them gives you the string minus the one character. Since we need state at each point in the iteration, we can't do anything like .scan.find, but we can manually break out of the loop on success. If we break, scan returns nil, otherwise it returns the string which is always truthy. \$\endgroup\$ Commented Jul 17, 2017 at 21:57
2
\$\begingroup\$

Java, 220 bytes

Try it online!

Golfed:

boolean t(String n){int l=n.length();if(f(x->{for(int i=2;i<x;)if(x%i++==0)return 1<0;return x>1;},new Integer(n)))if(l<2)return 1>0;else for(int i=0;i<l;)if(t(n.substring(0,i)+n.substring(++i,l)))return 1>0;return 1<0;}

Ungolfed:

 boolean t(String n) { int l = n.length(); if (f(x -> { for (int i = 2; i < x;) { if (x % i++ == 0) { return 1 < 0; } } return x > 1; } , new Integer(n))) { if (l < 2) { return 1 > 0; } else { for (int i = 0; i < l;) { if (t(n.substring(0, i) + n.substring(++i, l))) { return 1 > 0; } } } } return 1 < 0; }
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Ignore my previous comment. But you can golf it to this: boolean t(String n){int l=n.length(),x=new Integer(n),i;for(i=2;i<x;x=x%i++<1?0:x);if(x>1)if(l<2)return 1>0;else for(i=0;i<l;)if(t(n.substring(0,i)+n.substring(++i,l)))return 1>0;return 1<0;} (191 bytes) \$\endgroup\$ Commented Jul 18, 2017 at 6:54
  • \$\begingroup\$ You can save some bytes by returning 1 and 0 instead of true and false. \$\endgroup\$ Commented Jul 18, 2017 at 14:19
  • \$\begingroup\$ @Nevay That would work in C++, but not in Java. Integers cannot be implicitly converted to booleans. \$\endgroup\$ Commented Jul 18, 2017 at 15:26
  • 1
    \$\begingroup\$ Not sure but where does f come from? \$\endgroup\$ Commented Jul 18, 2017 at 17:09
  • \$\begingroup\$ The question states that any value may be used for true/false; the only place where you need a boolean result of the method is in the last if condition (where you can add >0 to convert the int to a boolean) which should save 2*2+1*4=8 bytes in Kevin Cruijssen's version. \$\endgroup\$ Commented Jul 18, 2017 at 23:28
2
\$\begingroup\$

Python 2, 132 124 119 bytes

-8 Thanks to @WheatWizard

-5 Thanks to @LeakyNun

p=lambda i:i>1and all(i%v for v in range(2,i)) f=lambda n:n<'0'or any(f(n[:i]+n[i+1:])for i in range(len(n)))*p(int(n))

Try it online!

Can't think of anything to hone it down without some builtin prime checker. Takes the number as a string (I assumed this given the OP allowed a list of digits, but if not then +14 bytes for another lambda), and recursively computes each "turtled" number's turtleness.

Improve this answer
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Shorter Primality test \$\endgroup\$ Commented Jul 17, 2017 at 18:13
  • \$\begingroup\$ I think f=lambda n,i=0:n==''or p(int(n))and i<len(n)and(f(n[:i]+n[i+1:])or f(n,i+1)) saves a byte. Someone with better Python golfing skills could probably shorten that further. \$\endgroup\$ Commented Jul 17, 2017 at 18:36
  • \$\begingroup\$ @Neil, it does save a byte, but the wording "the same output for any truthy or falsey value" prevents me from taking it, as inputting 1 returns 0 instead of False like the other cases (due to the -8 primality check). If the OP allows different (although synonymous) outputs, then I would change it up. \$\endgroup\$ Commented Jul 17, 2017 at 18:51
  • 1
    \$\begingroup\$ Sorry, my previous suggestion is invalid. 119 bytes \$\endgroup\$ Commented Jul 17, 2017 at 20:06
1
\$\begingroup\$

05AB1E, 28 27 bytes

Iterative solution.

¸[D0èg2‹#εæ¨D€gZQÏDpÏ}˜]p1å

Try it online!

Explanation

¸ # wrap input in a list [ # start a loop D0èg2‹# # if the length of the first element is less than 2, break ε # apply to each element in the list æ # compute powerset ¨ # remove last element (the full number) D€gZQÏ # keep only the elements whose length is the max length DpÏ # keep only primes } # end apply ˜ # flatten list ] # end loop p1å # is any element in the resulting list prime
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

C#, 355 bytes

namespace System{using B=Numerics.BigInteger;class A{static void Main(){Console.WriteLine(D(Console.ReadLine()));}static bool P(B x){if(x<2)return 1<0;B r=1;for(int i=1;i<=x-1;i++)r*=i;return(r+1)%x==0;}static bool D(string x){if(x.Length==0)return 1>0;bool b;if(b=P(B.Parse(x))){var n=1<0;for(int i=0;i<x.Length;i++)n|=D(x.Remove(i,1));b&=n;}return b;}}}

Try it online!

My first code golf, so I hope I did it alright. I couldn't think of a way to make it even smaller (other than using int instead of BigInteger, but I did it so it would work for all provided test cases). Anyway, here's the same properly formatted:

namespace System { using B = Numerics.BigInteger; class A { static void Main() { Console.WriteLine(D(Console.ReadLine())); } static bool P(B x) { if (x < 2) return 1<0; B r = 1; for (int i = 1; i <= x - 1; i++) r *= i; return (r + 1) % x == 0; } static bool D(string x) { if (x.Length == 0) return 1>0; bool b; if (b = P(B.Parse(x))) { var n = 1<0; for (int i = 0; i < x.Length; i++) n |= D(x.Remove(i, 1)); b &= n; } return b; } } }
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Perl 6, 65 bytes

my&f={.is-prime&&(10>$_||?grep {f +[~] .list},m:ex/^(.*).(.*)$/)}

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

PHP, 164 bytes

function t($n){for($i=1;++$i<$n;)if($n%$i<1)return 0;if($n<10)return $n>1;foreach($r=str_split($n)as$k=>$v){$q=$r;array_splice($q,$k,1);$z|=t(join($q));}return $z;}

Try it online!

Starts off by testing the number for primality, then loops through the digits as an array, popping each one out and joining the rest back together and feeding them recursively through the function again. Each link downwards does a logical OR with the lower paths, only returning true if there exists at least one path of all primes.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Javascript 167 bytes

n=>{a=[];for(i=1;i++<=n;)a.every(x=>i%x)?a.push(i):0;b=k=>(s=''+k,a.indexOf(k)>-1&&(k<10||[...s].some((x,i)=>(r=[...s],r.splice(i,1),b(~~(r.join('')))))));return b(n)}

Explanation

n=>{ a=[]; // create array to store primes in for(i=1;i++<=n;) // iterate from 2 to n a.every(x=>i%x)?a.push(i):0; // if i % x is truthy for all x in a, // then i is prime b=k=>( // function to test is k is turtle prime s=''+k, // convert k to a string a.indexOf(k)>-1 && ( // if k is prime and k<10 || // k is a single digit or [...s].some((x,i)=>( // iterate over the digits of k // and check to see if, by removing each // any of the resulting numbers is turtle prime // ... is spread operator // [...s] converts string s to an array of characters r=[...s], // convert s to an array again, // importantly, this cannot be the same array // we created above, as we need to r.splice(i,1), // splice out the ith element of the array b(~~(r.join(''))) // join the array to a string, convert to int, // and check if this number is turtle prime // ~ is bitwise negate, implicitly converts to int first before negating // ~~ negates the negation, getting us the int )) ) ); return b(n) } 

F=n=>{a=[];for(i=1;i++<=n;)a.every(x=>i%x)?a.push(i):0;b=k=>(s=''+k,a.indexOf(k)>-1&&(k<10||[...s].some((x,i)=>(r=[...s],r.splice(i,1),b(~~(r.join('')))))));return b(n)} $('#input').on('keyup', () => $('#output').text(F(parseInt($('#input').val(), 10))))
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <input type="text" id="input" /> <span id="output"></span>

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.