21
\$\begingroup\$

Inspired by Find the largest fragile prime.

By removing at least 1 digit from a positive integer, we can get a different non-negative integer. Note that this is different to the Remove function in the linked question. We say a prime number is delicate if all integers generated this way are not prime. For example, \$60649\$ generates the following integers:

0, 4, 6, 9, 49, 60, 64, 66, 69, 604, 606, 609, 649, 664, 669, 6049, 6064, 6069, 6649

None of these integers are prime, therefore \$60649\$ is a delicate prime. Note that any leading zeros are removed, and that the requirement is "not prime", so \$0\$ and \$1\$ both qualify, meaning that, for example, \$11\$ is a delicate prime.

Similar to the standard rule, you are to do one of the following tasks:

  • Given a positive integer \$n\$, output two distinct, consistent* values depending on whether \$n\$ is a delicate prime or not
  • Given a positive integer \$n\$, output the \$n\$th delicate prime
  • Given a positive integer \$n\$, output the first \$n\$ delicate primes
  • Output infinitely the list of delicate primes

*: You may choose to output two sets of values instead, where the values in the set correspond to your language’s definition of truthy and falsey. For example, a Python answer may output an empty list for falsey/truthy and a non-empty list otherwise.

You may choose which of the tasks you wish to do.

You can input and output in any standard way, and, as this is , shortest code in bytes wins

For reference, the first 20 delicate primes are:

2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949

A couple more to look out for:

821 - False (Removing the 8 and the 1 gives 2 which is prime)

I'll offer a +100 bounty for an answer which implements one of the standard I/Os rather than the method, that either:

  • is shorter than a naive implementation (please include such a version as proof if one hasn't already been posted)
  • or that doesn't rely on checking whether values are delicate primes or not when generating values (e.g. may use the fact that only specific digits can occur, or something else that isn't simply slapping a "loop over numbers, finding delicate primes")

This is kinda subjective as to what counts as "checking for delicate primes", so I'll use my best judgement when it comes to awarding the bounty.

\$\endgroup\$
  • 1
    \$\begingroup\$ The question states "given a prime number \$n\$..." but the first output option states "given a positive integer \$n\$..." If we choose the first output option, is the input guaranteed to be prime? \$\endgroup\$ – Robin Ryder Sep 20 at 19:37
  • \$\begingroup\$ @RobinRyder That's a bit of confusing wording on my part. The input will always be a positive integer (not necessarily prime), the "given a prime number \$n\$..." is part of the explanation, changing now \$\endgroup\$ – caird coinheringaahing Sep 20 at 19:38
  • \$\begingroup\$ "two distinct, consistent values depending on whether n is a delicate prime or not" - can we not use our languages truthy/falsey definition? \$\endgroup\$ – Jonathan Allan Sep 20 at 23:35
  • \$\begingroup\$ @JonathanAllan I’m loathe to say “no” to reasonable I/O requests, so I think I’ll say that truthy/falsey values count as distinct values, so long as one is consistently truthy and the other consistently falsey. It’s a bit unconventional, but I think that should work as best as possible \$\endgroup\$ – caird coinheringaahing Sep 20 at 23:40
  • 2
    \$\begingroup\$ As per default consensus the outputs would have to be consistently truthy and consistently falsey, it's just they would not necessarily need be distinct - e.g. Python could return a list which is populated (possibly differently for different inputs) as a truthy result, and an empty list as a falsey result, etc. \$\endgroup\$ – Jonathan Allan Sep 20 at 23:51

16 Answers 16

10
\$\begingroup\$

05AB1E, 4 bytes

Code

Uses the 05AB1E-encoding. Checks whether the given number is a delicate prime or not.

æpJΘ

Try it online! or Check for all numbers between 1 and 9949.

Explanation

æ      # Get the powerset of the number.
 p     # Check for each element whether it is a prime.
  J    # Join these numbers into one big number.
   Θ   # Check whether this joined number is equal to 1.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I don't think you even need Θ since truthy/falsey is allowed (only confirmed in comments at present). \$\endgroup\$ – Jonathan Allan Sep 21 at 0:20
  • 1
    \$\begingroup\$ @JonathanAllan Thanks for the heads up! The last byte is indeed solely for making sure that it outputs only 2 distinct values. I'll adjust the code when this condition has been changed in the main post. \$\endgroup\$ – Adnan Sep 21 at 0:26
  • \$\begingroup\$ @Adnan I’ve clarified my comment in the main post \$\endgroup\$ – caird coinheringaahing Sep 21 at 8:33
  • \$\begingroup\$ Out of curiosity: why do you use an infinite list and then take the first 20 items in your TIO, instead of just filtering on the [1,10000] list directly (i.e. like this)? \$\endgroup\$ – Kevin Cruijssen Sep 21 at 10:11
9
\$\begingroup\$

APL (Dyalog Extended), 16 14 bytes

</1⍭⍎⍕(⊢,,¨)\⍞

Try it online!

-2 bytes (∊⍎¨¨ → ⍎⍕) thanks to @ngn.

Full program that takes a single number from stdin and prints 1 (true) or 0 (false).

The trick here is how it generates all non-empty subsequences:

  • (⊢,,¨)/ str gives all subsequences of str which include the last character.
  (⊢,,¨)/ '1234'
→ '1' (⊢,,¨) '2' (⊢,,¨) '3' (⊢,,¨) '4'
→ '1' (⊢,,¨) '2' (⊢,,¨) '4' '34'
→ '1' (⊢,,¨) '4' '34' '24' '234'
→ '4' '34' '24' '234' '14' '134' '124' '1234'
  • (⊢,,¨)\ str applies (⊢,,¨)/ to each prefix of str, giving all non-empty subsequences as a list of lists of strings.
  (⊢,,¨)\ '1234'
→ '1' ('2' '12') ('3' '23' '13' '123') ('4' '34' '24' '234' '14' '134' '124' '1234')

Explanation of whole code:

</1⍭⍎⍕(⊢,,¨)\⍞
             ⍞  ⍝ Take n from stdin as a string
      (    )\   ⍝ For each prefix, reduce from right by
         ,¨     ⍝   prepend the previous char to each string
       ⊢,       ⍝   and append to the previous list of strings
    ⍎⍕          ⍝ Convert nested strings to a single string,
                ⍝ and then eval it to get a simple integer vector
  1⍭  ⍝ Test each number for primality
</    ⍝ Test if the only truth is the last one
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I'm missing something... How do we get "all possible subsets" from "all prefixes"? I'm guessing it's "prepend the previous char to each string" but I'm not seeing it clearly. \$\endgroup\$ – Jonah Sep 21 at 2:06
  • 1
    \$\begingroup\$ @Jonah Added an explanation. \$\endgroup\$ – Bubbler Sep 21 at 2:24
  • \$\begingroup\$ Thanks Bubbler. It looks like the J equivalent of (⊢,,¨) is not as nice because of boxing: ([:,(];,)&>)/. Can you see a way to shorten it? \$\endgroup\$ – Jonah Sep 21 at 3:34
  • 2
    \$\begingroup\$ Actually, if you box the argument first you can do (],,&.>)/ which is much more parallel to yours. \$\endgroup\$ – Jonah Sep 21 at 3:40
7
\$\begingroup\$

Brachylog, 7 6 bytes

ṗ⊇ᵘṗˢȮ

Try it online!

ṗ⊇ᵘṗˢȮ the implicit input
ṗ      is a prime
 ⊇ᵘ    and from every unique subset
   ṗˢ  select the primes
     Ȯ and this should be a list with one element (the prime input itself)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ If ⊇ᵘṗˢ on its own is a list of the primes in the unique subset is there not a one-byte addition that can assert that this is [?]? \$\endgroup\$ – Jonathan Allan Sep 20 at 23:23
  • 1
    \$\begingroup\$ @JonathanAllan I can't think of one, the constants don't have something with ?. (In the answer history is a 7 byte solution exactly like yours: ⊇ᵘṗˢ[?].) What could work is using e.g. 60649 as both input and output with ⊇ᵘṗˢ⌋. But I thought that would be like taking two arguments. \$\endgroup\$ – xash Sep 20 at 23:35
  • 1
    \$\begingroup\$ Hmm, indeed I'm also not sure having to give the input twice would be acceptable. (I would have thought with no Z argument that would be the default behaviour of Brachylog :/) \$\endgroup\$ – Jonathan Allan Sep 20 at 23:42
  • \$\begingroup\$ For what it's worth, ⊇ᵘṗˢ[?] could also be ⊇ᵘṗˢ~g?, still 7 bytes. \$\endgroup\$ – Unrelated String Sep 21 at 4:49
5
\$\begingroup\$

Jelly, 7 bytes

DŒPḌẒḄ’

A monadic Link accepting a positive integer which returns zero (falsey) if it's a delicate prime, or a non-zero integer (truthy) if not.

Try it online! Or see the first twenty.

How?

DŒPḌẒḄ’ - Link: n         e.g. 824                      409
D       - decimal digits       [8,2,4]                  [4,0,9]
 ŒP     - power-set            [[],[8]...,[8,2,4]]      [[],[4],...,[4,0,9]]
   Ḍ    - undecimal            [0,8,2,4,82,84,24,824]   [0,4,0,9,40,49,9,409]
    Ẓ   - is prime?            [0,0,1,0,0,0,0,0]        [0,0,0,0,0,0,0,1]
     Ḅ  - from binary          32                       1
      ’ - decrement            31                       0
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Ah, converting from binary’s a clever trick! I was trying to figure out how to shorten “is only the last element 1?”. Also, I think you can replace the last 2 bytes with to decrement it and output a falsey value for delicate primes and truthy otherwise \$\endgroup\$ – caird coinheringaahing Sep 21 at 0:02
  • \$\begingroup\$ I was thinking of that, was just waiting on your confirmation. \$\endgroup\$ – Jonathan Allan Sep 21 at 0:04
5
\$\begingroup\$

Japt, 7 bytes

¥à f_°j

Try it or test [0,1000)

¥à f_°j     :Implicit input of integer string
¥           :Is equal to
 à          :Combinations
   f        :Filter
    _       :By passing each through a function
     °      :Postfix increment, to cast to an integer
      j     :Is prime?
| improve this answer | |
\$\endgroup\$
  • 3
    \$\begingroup\$ I read the language as Jelly initially, and was impressed and confused trying to figure out how it worked :/ \$\endgroup\$ – caird coinheringaahing Sep 20 at 21:57
  • \$\begingroup\$ Explanation added, @cairdcoinheringaahing. \$\endgroup\$ – Shaggy Sep 21 at 8:55
4
\$\begingroup\$

J, 25 23 bytes

-2 thanks to Jonah!

Returns a list containing either 1 being truthy or 0 otherwise.

1</@p:(#~2#:@i.@^#)&.":

Try it online!

How it works

1</@p:(#~2#:@i.@^#)&.":
                   &.": convert the number to a string
      (  2      ^#)      2 ^ length
          #:@i.@         enumerated and to base 2
       #~                select from the string based on the bit mask
                   &.": convert from strings to numbers
1   p:                  primes -> 1, non-primes -> 0
                         so in the delicate prime case, we have
                         (2^L) - 1 zeros and one 1 for the input itself
 </@                    reduce from left to right with less-than
                         (so last position is 1, everything else 0)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Really like </@ here. Since it's a decision problem you can get 23 bytes \$\endgroup\$ – Jonah Sep 20 at 21:57
4
\$\begingroup\$

Pyth, 14 8 bytes

qjfP_sTy

Try it online!

Explanation

qjfP_sTy
  f       # filter
       y  # all subsets of input
   P_sT   # with a primality test
 j        # join result of filter on newlines
q         # check if it equals input
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Retina 0.8.2, 53 bytes

^
;
+%`;(.)
$1;$'¶$`;
.+
$*
%A`^.?$|^(..+)\1+$
^1+¶+$

Try it online! Link includes test cases. Explanation:

^
;
+%`;(.)
$1;$'¶$`;

Generate all subsequences of the input.

.+
$*

Convert then to unary.

%A`^.?$|^(..+)\1+$

Delete the ones that aren't prime, but don't delete the newlines. (A multiline replace also works, but is harder to format an explanation for.)

^1+¶+$

Check that the original input was prime but none of the proper subsequences were.

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

Scala, 173 170 bytes

n=>(s"$n".indices.toSet.subsets.filter{x=>1<x.size&x.size<s"$n".size}.map(_.toSeq.sorted.map(""+n).mkString.toInt).toSet+n).filter{x=>x>1&2.to(x/2).forall(x%_>0)}==Set(n)

Try it online!

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

R, 163 154 bytes

function(x,n=nchar(x),s=sum)(a=apply(!expand.grid(rep(list(0:1),n)),1,function(v)(y=s((x%/%10^(n:1-1)%%10)[v]*10^(s(v):1-1)))&s(!y%%1:y)==2))[1]&!s(a[-1])

Try it online!

Checks for primes among the numbers formed by removing all combinations of digits from x. The first combination is removal of no digits: this must be TRUE, and all other prime tests must be FALSE.

Commented:

is_delicate_prime=
function(x,                     # x = number to test
 n=nchar(x),                    # n = number of digits of x
 s=sum)                         # s = alias to sum() function
(a=                             # a = matrix of all prime-tests:
 apply(                         #     apply the function v to each of...
  !expand.grid(rep(list(0:1),n)),   # all combinations of n of TRUE/FALSE...
  1,                            #     row-by-row...
  function(v)                   #     defining the output of v as:
   (y=s((x%/%10^(n:1-1)%%10)    #       the digits of x...
    [v]                         #       (considering only the elements chosen by v)... 
       *10^(s(v):1-1)))         #       multiplied by 10^((v-1)..0)...
   &s(!y%%1:y)==2))             #       tested for primality AND non-zero
[1]                             # Finally, output TRUE if a[1] is TRUE...
   &!s(a[-1])                   # and the sum of all other elements of a are FALSE
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 54 bytes

Select[FromDigits/@Subsets@@RealDigits@#,PrimeQ]=={#}&

Try it online!

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

JavaScript (ES6),  98  95 bytes

Expects n as a string. Returns a Boolean value.

n=>[...n].reduce((a,x)=>[...a,...a.map(y=>(g=k=>y%--k?g(k):(p+=q=y>1&k<2,y))(y+=x))],[p=0])|q/p

Try it online!

How?

We compute the powerset of the digits of n in such a way that the order is preserved and n itself is computed last. The result is true if the only prime among the resulting integers is the last one.

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

Python 2, 139 \$\cdots\$ 145 142 bytes

Added 36 bytes to fix a bug kindly pointed out by pxeger.
Saved 5 bytes thanks to pxeger!!!

lambda n,R=range:all((g<2or any(g%i<1for i in R(2,g)))-(`g`==n)for g in{int(''.join(n[j]for j in R(len(n))if i>>j&1))for i in R(1,2**len(n))})

Try it online!

Inputs an integer as a string and returns True if it's a delicate prime or False otherwise.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Goddammit! I was just about to post my Python 3 solution, which is almost the exact same! The R=range trick is genius. You can replace the and with * since True == 1 in Python and truthy/falsey values are allowed. \$\endgroup\$ – pxeger Sep 21 at 9:09
  • \$\begingroup\$ Actually I just noticed that your solution isn't actually correct, I'm still trying to work out why exactly... \$\endgroup\$ – pxeger Sep 21 at 9:12
  • \$\begingroup\$ You're not checking that the initial input number itself is prime. \$\endgroup\$ – pxeger Sep 21 at 9:43
  • 1
    \$\begingroup\$ @pxeger Ooops, thought we only had prime inputs - fixing that... \$\endgroup\$ – Noodle9 Sep 21 at 10:23
  • \$\begingroup\$ @pxeger All fixed and nice one - thanks! :D \$\endgroup\$ – Noodle9 Sep 21 at 10:47
2
\$\begingroup\$

Python 3.8 (pre-release), 146 144 bytes

-2 bytes by removing redundant parentheses

I was also working on a very similar answer just before Noodle9 posted theirs, and I combined ideas from that to get this (upvote it!). That one is now quite different because they initially had a broken one, so I thought I'd post mine.

lambda s,R=range:(l:=len(s))*all((g!=int(s))^(g>1)&all(g%k for k in R(2,g))for g in{int(''.join(s[j]for j in R(l)if i>>j&1))for i in R(1,2**l)})

Try it online!

Explanation:

lambda s,R=range:(l:=len(s))*all((g!=int(s))^(g>1)&all(g%k for k in R(2,g))for g in{int(''.join(s[j]for j in R(l)if i>>j&1))for i in R(1,2**l)})

lambda s        :                                                                                                                                       function
        ,R=range                                                                                                                                        alias `range` built-in to `R`
                                                                                   {            s[j]for j in R(l)if i>>j&1  for i in R(1,2**l)}         compute the power-set (excluding the empty set)
                                                                                    int(''.join(                          ))                            convert each list of digits to an integer
                             all(                                          for g in                                                            )        check the integers for primality
                                                    all(g%k for k in R(2,g))                                                                            check for factors in the number
                                              (g>1)&                                                                                                    makes sure 0 and 1 aren't treated as prime
                                 (g!=int(s))^                                                                                                           ensure the number itself is prime
                 (l:=len(s))*                                                                                                                           store the length in `l`

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

SageMath, 139 bytes

def f(n):s=str(n);l=len(s);return p(n)*all(~-p(g)for g in{int(''.join(s[j]for j in R(l)if i>>j&1))for i in R(1,2**l-1)})
R=range;p=is_prime

Try it online!

Port of my Python answer.

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

Python 3, 181 bytes

Using itertools and a golfed recipe for powerset.

lambda s,R=range:all(p(int(''.join(t)),R)for t in sum(([*combinations(s,k)]for k in R(1,len(s))),[]))>p(int(s),R)
from itertools import*
p=lambda n,R:any(n%i<1for i in R(2,n))or 2>n

Try it online!

Expects input as a string.

The function p returns True if its input is not prime, and False if it is prime; the main function returns (forall t, p(t)) > p(s) where t takes all the "subvalues" of s. The only way for booleans to satisfy this inequality is True > False, which means all t are nonprimes and s is not nonprime.

Disclaimer: There were already two python answers when I posted this one.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Don’t worry about existing answers. So long as they aren’t exact duplicates, there’s no issue and it’s always interesting to see different approaches to the same challenge \$\endgroup\$ – caird coinheringaahing Sep 22 at 11:26

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.