36
\$\begingroup\$

Challenge

Given an input integer n > 0, output the number of primes (other than n, if n itself is prime) that can be produced by altering one digit in the decimal expansion of n (without changing the number of digits).

Examples

For example, n = 2. By altering one digit in the decimal expansion of 2, we can come up with three additional prime numbers, 3, 5, 7, so a(n) = 3.

For another example, n = 13. By altering one digit, you can get primes 11, 17, 19, 23, 43, 53, 73, 83, so a(13) = 8.

For a final example, n = 20. By altering one digit, you can get primes 23, 29, so a(20) = 2.

Sequence

Here are the first 20 terms to get you started. This is OEIS A048853.

4, 3, 3, 4, 3, 4, 3, 4, 4, 4, 7, 4, 8, 4, 4, 4, 7, 4, 7, 2

Rules

  • The input and output can be assumed to fit in your language's native integer type.
  • The input and output can be given in any convenient format.
  • Ignore leading zeros (for example, 03 is not a prime number under this formulation).
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • If possible, please include a link to an online testing environment so other people can try out your code!
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
\$\endgroup\$
  • 4
    \$\begingroup\$ I'm trying to think of the smallest n for which the output is 0. I think it's n = 200. I also think they come in bunches: 200,202,204,206,208, 320,322,...,328, 510,...,518, 620,...628, 840,...,848, etc. \$\endgroup\$ – Engineer Toast Aug 2 '17 at 16:24
  • \$\begingroup\$ Does "The input and output can be assumed to fit in your language's native integer type" states that we are not allowed to take input as string? \$\endgroup\$ – Dead Possum Aug 2 '17 at 16:39
  • 1
    \$\begingroup\$ @DeadPossum No, that's allowed. Just that you don't need to worry about 2^100 as input if you only are using 32-bit integers, for example. \$\endgroup\$ – AdmBorkBork Aug 2 '17 at 16:41
  • \$\begingroup\$ Do let me know if I'm going overboard... I have 3 different submissions now \$\endgroup\$ – Patrick Roberts Aug 2 '17 at 21:41
  • 2
    \$\begingroup\$ @EngineerToast After finding the first example prime (294001), I finally thought of looking it up on OEIS: A192545 and A158124. Also relevant: A143641. \$\endgroup\$ – Ørjan Johansen Aug 4 '17 at 17:17

17 Answers 17

10
\$\begingroup\$

05AB1E, 17 16 14 11 bytes

ā°`<Ÿʒ.L}pO

Explanation:

ā             Push inclusive range from 1 to the length of the input
 °            Raise 10 to the power of each element
  `           Push each element to the stack
   <          Decrement the topmost element
    Ÿ         Inclusive range
              For 13, this creates an array like [10 11 12 13 14 .. 98 99]
     ʒ.L}     Only keep elements with a levenshtein distance to the input of
              exactly one
         p    Check each element for primality
          O   Sum

Try it online! or up to 100.

\$\endgroup\$
  • 1
    \$\begingroup\$ .L? Seriously? .L?!?! \$\endgroup\$ – Erik the Outgolfer Aug 3 '17 at 12:04
  • \$\begingroup\$ @EriktheOutgolfer L. \$\endgroup\$ – Okx Aug 3 '17 at 16:16
  • \$\begingroup\$ I mean, there's a builtin for levenshtein distance! \$\endgroup\$ – Erik the Outgolfer Aug 3 '17 at 16:47
  • \$\begingroup\$ @EriktheOutgolfer ¯\_(ツ)_/¯ \$\endgroup\$ – Okx Aug 3 '17 at 16:58
  • \$\begingroup\$ I know it's been a while, but you can remove the < to save a byte. Even if the filter doesn't remove the 100/1000/10000/etc., it's never a prime anyway so won't affect the output. \$\endgroup\$ – Kevin Cruijssen May 15 at 13:01
5
\$\begingroup\$

Python 2, 146 136 127 121 118 bytes

Thanks to @Mr.Xcoder for suggestions

lambda I:sum(all(i%v for v in range(2,i))*sum(z!=x for z,x in zip(I,`i`))==1for i in range(1+10**~-len(I),10**len(I)))

Explanation:

Generate numbers with length equal to input length, skipping first (1,10,100,1000,... )

for i in range(1+10**~-len(I),10**len(I))

Check that generated number differs from input by only one digit

sum(z!=x for z,x in zip(I,`i`))==1

Check for prime

all(i%v for v in range(2,i))

Count

sum(...)    

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Might it be shorter to not make this a lambda, and do r=range, since you use it many times...? \$\endgroup\$ – Stewie Griffin Aug 2 '17 at 15:01
  • 1
    \$\begingroup\$ Does this work for things like 143? Because I see range(1,10), that excludes 0, and 103 is prime \$\endgroup\$ – Mr. Xcoder Aug 2 '17 at 15:01
  • \$\begingroup\$ @Mr.Xcoder fixed \$\endgroup\$ – Dead Possum Aug 2 '17 at 15:11
  • 1
    \$\begingroup\$ You do not need 0 in r(0,10). r(10) suffices. \$\endgroup\$ – Mr. Xcoder Aug 2 '17 at 15:13
  • 1
    \$\begingroup\$ Also, I suggest putting it as such: lambda I,r=range: \$\endgroup\$ – Mr. Xcoder Aug 2 '17 at 15:14
4
\$\begingroup\$

Javascript (ES6) 148 bytes

Takes the input as a string and returns as a number

n=>(n.replace(/./g,"$`a$' ").split` `.map(s=>s&&[..."0123456789"].map(d=>r+=+(t=s.replace(/a/,d))[0]&&t^n&&(p=v=>t>1&(--v<2||t%v&&p(v)))(t)),r=0),r)

Example code snippet:

f=
n=>(n.replace(/./g,"$`a$' ").split` `.map(s=>s&&[..."0123456789"].map(d=>r+=+(t=s.replace(/a/,d))[0]&&t^n&&(p=v=>t>1&(--v<2||t%v&&p(v)))(t)),r=0),r)

for(var k=1;k<=20;k++)
  o.innerText+=f(""+k)+" "
<pre id=o></pre>

\$\endgroup\$
4
\$\begingroup\$

Jelly, 21 18 15 bytes

3 bytes thanks to Dennis.

æḟ⁵æR×⁵$DnDS€ċ1

Try it online! or Verify all testcases.

\$\endgroup\$
  • \$\begingroup\$ æḟ⁵æR×⁵$DnDS€ċ1 saves a few bytes. \$\endgroup\$ – Dennis Aug 2 '17 at 18:34
  • \$\begingroup\$ The alternative range is quite clever. \$\endgroup\$ – Leaky Nun Aug 2 '17 at 18:55
3
\$\begingroup\$

Mathematica, 105 bytes

F=Count[Range[f=IntegerDigits;g=10^Length@f@#/10,10g],n_/;PrimeQ@n&&MatchQ[f@n-f@#,{x=0...,_,x}]&&n!=#]&;

Try it online!

Function which expects a positive integer #. Sets f equal to the function IntegerDigits which returns the list of digits of its input. We take the Range from g to 10g (inclusive), where g=10^Length@f@#/10 is the largest power of 10 less than or equal to the input #, then Count the n such that PrimeQ@n&&MatchQ[f@n-f@#,{x=0...,_,x}]&&n!=#. PrimeQ@n checks whether n is prime, MatchQ[f@n-f@#,{x=0...,_,x}] checks whether the difference between the list of digits of n and # is of the form {0..., _, 0...}, and n!=# ensures that n and # are Unequal.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 153 142 139 bytes

n=>([...n].map((c,i,[...a])=>[...''+1e9].map((u,j)=>s+=j+i&&j!=c?p((a.splice(i,1,j),a.join``)):0),s=0,p=q=>eval('for(k=q;q%--k;);k==1')),s)

Accepts input as a string. Undefined behavior for invalid input, though it should terminate without error on any string I can think of. Not necessarily before the heat-death of the universe though, particularly for long strings.

Demo

f=
n=>([...n].map((c,i,[...a])=>[...''+1e9].map((u,j)=>s+=j+i&&j!=c?p((a.splice(i,1,j),a.join``)):0),s=0,p=q=>eval('for(k=q;q%--k;);k==1')),s)
console.log([...''+1e19].map((_,i)=>f(i+1+'')).join())
i.onchange=()=>console.log(f(i.value))
<input id=i>

Improvements

Saved 11 bytes by refactoring the reduce() calls into map() calls, and by implicitly copying the array a in the function parameter, instead of in within the context of the splice() call.

Saved 3 bytes thanks to @Neil's suggestion to convert [...Array(10)] to [...''+1e9].

Unminified code

input => (
  [...input].map(
    (char, decimal, [...charArray]) =>
      [...'' + 1e9].map(
        (unused, digit) => sum +=
          digit + decimal && digit != char ?
            prime(
              (
                charArray.splice(decimal, 1, digit)
                , charArray.join``
              )
            ) :
            0
      )
    , sum = 0
    , prime = test => eval('for(factor = test; test % --factor;); factor == 1')
  )
  , sum
)

Explanation

The function uses a two-level map() to sum the amount of permutations that pass the primality test, which was borrowed and modified from this answer.

(Original answer)

reduce((accumulator, currentValue, currentIndex, array) => aggregate, initialValue)

So for example, to calculate the sum of an array, you would pass an initialValue of 0, and return an aggregate equal to accumulator + currentValue. Modifying this approach slightly, we instead calculate the number of permutations that pass the primality test:

reduce(
  (passedSoFar, currentDecimal, currentIndex, digitArray) =>
    isValidPermutation() ?
      passedSoFar + prime(getPermutation()) :
      passedSoFar
  , 0
)

That is essentially the inner reduce(), which iterates all the permutations of the digitArray by changing each decimal to a specific permutatedDigit. We then need an outer reduce() to iterate all possible permutatedDigit's with which to replace each decimal, which is just 0-9.

Abnormalities in implementation

[...''+1e9].map((u,j)=>... was the shortest way @Neil could think of to iterate an argument 0 through 9. It would be preferable to do so with u, but u is not useful for each element in the array, in this case.

i+j in the ternary condition checks to ensure that 0 is not a possible permutation of the leading digit, as per the challenge specification. j!=c ensures that the original n is not a candidate to go through the primality test.

(a.splice(i,1,j),a.join``) is kind of a mess. splice() replaces the digit at decimal == i with the permutatedDigit == j, but since splice() returns the removed elements (in this case, would be equal to [a[i]]) instead of the modified array, we must use the comma operator to pass the modified array a to the primality test, but not before join()ing it into a number string.

Lastly, the eval() is to save a byte since, compared to the more canonical approach, it is shorter:

q=>eval('for(k=q;q%--k;);k==1')

q=>{for(k=q;q%--k;);return k==1}

The reference to the prime test p is initialized in an unused argument to the map() call.

\$\endgroup\$
  • \$\begingroup\$ I think the tips page says [...''+1e9] is shorter. \$\endgroup\$ – Neil Aug 3 '17 at 9:30
2
\$\begingroup\$

Python 2, 134 bytes

lambda x,r=range,l=len:sum(~-f*(~-l(x)==sum(`f`[t]==x[t]for t in r(l(x))))and all(f%v for v in r(2,f))for f in r(10**~-l(x),10**l(x)))

Try it online!

More elegant, longer version:

lambda x,r=range,l=len:l(filter(lambda f:(~-f*(~-l(x)==sum(`f`[t]==x[t]for t in r(l(x)))))*all(f%v for v in r(2,f)),r(10**~-l(x),10**l(x))))

The input is taken as a String.


Explanation (older version)

  • lambda x,r=range,l=len: - Defines a lambda with a String parameter x and two constant parameters r=range and l=len.

  • sum(1...) - Get the length, which saves 1 byte over len([...]).

  • for f in r(10**~-l(x),10**l(x)) - Generates absolutely all the numbers with the same order of magnitude as the input (expect for 0). For instance, an input of 3, would result in [1, 2, 3, 4, 5, 6, 7, 8, 9].

  • sum(1for t in r(l(x))if`f`[t]==x[t])==~-l(x)and f>1 - Checks if the current number is exactly 1 digit away from the input, and that it is higher than 1.

  • all(f%v for v in r(2,f)) - Checks if the current number is prime.

\$\endgroup\$
  • 1
    \$\begingroup\$ You cound change sum(1for..ifBOOL) to sum(BOOLfor) to save some bytes \$\endgroup\$ – Dead Possum Aug 2 '17 at 16:34
  • \$\begingroup\$ Are we allowed to take input as string? Looking at "The input and output can be assumed to fit in your language's native integer type" I'm not sure \$\endgroup\$ – Dead Possum Aug 2 '17 at 16:38
  • \$\begingroup\$ @DeadPossum Some of the answers do. Why wouldn't it be allowed?! \$\endgroup\$ – Mr. Xcoder Aug 2 '17 at 16:39
  • \$\begingroup\$ I'm ran out of votes for today, but will +1 asap :D \$\endgroup\$ – Dead Possum Aug 2 '17 at 16:46
  • \$\begingroup\$ @DeadPossum Sure. Don't forget or I'll ping you! (</joke>) \$\endgroup\$ – Mr. Xcoder Aug 2 '17 at 16:47
1
\$\begingroup\$

JavaScript (ES6), 137 bytes

i=(a=prompt()).length;s=0;while(i--)for(j=0;j<=9;j++){(b=[...a]).splice(i,1,j);k=b=b.join('');while(b%--k);s+=i+j&&a[i]!=j&&k==1}alert(s)

Adapts my other answer into a full-program submission using the Web API methods prompt() and alert().

\$\endgroup\$
1
\$\begingroup\$

Bean, 126 bytes

00000000: a64d a065 8050 80a0 5d20 8001 a64d a06f  ¦M e.P. ] ..¦M o
00000010: 8025 39b5 cb81 2065 27a6 4da0 6680 2581  .%9µË. e'¦M f.%.
00000020: 0035 cb81 2066 27a6 53d0 80cd a05e 8043  .5Ë. f'¦SÐ.Í ^.C
00000030: cf20 5d00 2080 82a0 65a5 3a20 66a6 4da0  Ï ]. .. e¥: f¦M 
00000040: 6780 4da0 5e80 53d0 80a0 5e20 807b 2300  g.M ^.SÐ. ^ .{#.
00000050: b5cc a05e 8f4b c120 6728 264d a06f 814e  µÌ ^.KÁ g(&M o.N
00000060: cecc a065 8b20 6681 4cd0 84a0 5d20 6581  ÎÌ e. f.LÐ. ] e.
00000070: 2066 814c a067 8025 3a26 206f b130        f.L g.%:& o±0

Try it online!

An adaption of my full-program JavaScript submission.

JavaScript Equivalent

i=a.length
s=0
while(i--){
  j=10
  while(j--){
    (b=[...a]).splice(i,1,j)
    k=b=b.join('')
    while(b%--k);
    s+=i+j&&a[i]!=j&&k==1
  }
}
s

Explanation

a is implicitly initialized as the first line of input as a string and the last statement s is implicitly output, which contains the sum of prime permutations.

\$\endgroup\$
1
\$\begingroup\$

Husk, 32 bytes

Lof§&ȯ=1Σzo±≠d⁰o=Ld⁰L↑o≤Ld⁰Lmdİp

Try it online!

Ungolfed/Explanation

                              İp  -- get all primes
                            md    -- and convert them to list of digits
                     ↑o≤   L      -- take as long as the lenghth of these digit lists are ≤ ..
                        Ld⁰       -- .. the number of digits of input 
 of                               -- from those primes filter:
               o=Ld⁰L             --   same number of digits as input
   §&                             --   and
        Σz                        --   the number of..
          o±≠d⁰                   --   .. digits that differ from input digits ..
     ȯ=1                          --   .. must be one
L                                 -- finally count them
\$\endgroup\$
1
\$\begingroup\$

Japt, 28 23 bytes

-5 bytes thanks to @ETHproductions.

¬x@AÇ|Y©+UhYZsÃâ kUn)èj

Takes a string as input.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Perhaps another couple with ¬x@AÇ|Y©+UhYZsÃâ kUn)èj? \$\endgroup\$ – ETHproductions Aug 4 '17 at 1:29
1
\$\begingroup\$

PHP, 151 147 141 140 136 134 129 128 bytes

-6 bytes thanks to @Einacio; -1 byte thanks to @Titus

<?php for($i=$m=10**strlen($n=$argv[1]);$i-->$m/10;)if(levenshtein($n,$i)==$f=$t=1){while($t<$i)$f+=$i%$t++<1;$c+=$f==2;}echo$c;

Try it online!

Formatted, with comments:

<?php
// Work through each integer with the same number of digits as the input $argv[1].
for ($i = $m = 10 ** strlen($n = $argv[1]); $i-- > $m / 10;)
    // Is it exactly one digit different from the input?
    if (levenshtein($n, $i) == $f = $t = 1) {
        // Count its factors.
        while ($t < $i) $f += $i % $t++ < 1;
        // If there are exactly 2 factors then it's a prime, so increment the counter.
        $c += $f == 2;
    }
// Print the final count.
echo $c;

To keep it as short as I could, I've:

  • combined assignments $f = $t = 1;
  • snook in a ++ increment as part of another expression $f += $i % $t++ == 0 (the increment is executed after the modulus operation and so does not affect its result);
  • and rather than using an if statement for a conditional increment have utilised the fact that boolean true when cast as an integer becomes 1, using $c += $f == 2; rather than if ($f == 2) $c++;.
\$\endgroup\$
  • 1
    \$\begingroup\$ you don't need to define $c, it counts as 0 on the first += \$\endgroup\$ – Einacio Aug 3 '17 at 13:25
  • \$\begingroup\$ @Einacio What are the golf rules? Is that allowed, as it gives an undefined variable warning notice? \$\endgroup\$ – WebSmithery Aug 3 '17 at 13:43
  • \$\begingroup\$ @Einacio Apparently any output to STDERR can be ignored, so thanks for the suggestion. \$\endgroup\$ – WebSmithery Aug 3 '17 at 16:21
  • 1
    \$\begingroup\$ +1 for use of levenshtein. Nice idea! $i%$t++<1 is shorter than $i%$t++==0. \$\endgroup\$ – Titus Aug 4 '17 at 3:26
1
\$\begingroup\$

Perl 6, 83 bytes

{+grep &is-prime,m:ex/^(.*)(.)(.*)$/.map:{|map
.[0]~*~.[2],grep *-.[1],?.[0]..9}}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ How about using X~ instead of map? 81 bytes \$\endgroup\$ – Jo King May 16 at 4:37
0
\$\begingroup\$

PHP, 100+1 bytes

for(;~($a=$argn)[$i];$i++)for($d=-!!$i;$d++<9;$c+=$k==1)for($a[$i]=$d,$k=$a;--$k&&$a%$k;);echo$c-$i;

Run as pipe with -nR or try it online.

breakdown

for(;~($n=$argn)[$i];$i++)  # loop through argument digits, restore $n in every iteration
    for($d=-!!$i;               # loop $d from 0 (1 for first digit)
        $d++<9;                 # ... to 9
        $c+=$k==1                   # 3. if divisor is 1, increment counter
    )
        for($n[$i]=$d,              # 1. replace digit
            $k=$n;--$k&&$n%$k;      # 2. find largest divisor of $n smaller than $n
        );
echo$c-$i;                  # print counter - length
\$\endgroup\$
0
\$\begingroup\$

Java 8, 201 194 bytes

n->{String s=n+"";int r=0,i=0,j,k,t,u,l=s.length();for(;i<l;i++)for(j=0;++j<10;r+=n==u|t<2?0:1)for(u=t=new Integer(s.substring(0,i)+j+(i<l?s.substring(i+1):"")),k=2;k<t;t=t%k++<1?0:t);return r;}

Explanation:

Try it here.

n->{                        // Method with integer as parameter and return-type
  String s=n+"";            //  String representation of the input-int
  int r=0,                  //  Result-integer
      i=0,j,k,              //  Index-integers
      t,u,                  //  Temp integers
      l=s.length();         //  Length of the String
  for(;i<l;i++)             //  Loop (1) from 0 to `l` (exclusive)
    for(j=0;++j<10;         //   Inner loop (2) from 1 to 10 (exclusive)
        r+=                 //     And after every iteration, raise the result by:
           n==u             //      If the current number equals the input
           |t<2?            //      or it is not a prime:
            0               //       Add nothing to the result-counter
           :                //      Else:
            1)              //       Raise the result-counter by one
      for(                  //    Inner loop (3)
          u=t=              //     First set both `u` and `t` to:
              new Integer(  //      Convert the following String to an integer: 
               s.substring(0,i)
                            //       Get the substring from 0 to `i` (exclusive)
               +j           //       + `j`
               +(i<l?       //       + If `i` is smaller than the String-length:
                  s.substring(i+1)
                            //          The substring from 0 to `i` (inclusive)
                 :          //         Else:
                  "")),     //          Nothing
          k=2;              //     And start `k` at 2
              k<t;          //     Continue looping as long as `k` is smaller than `t`
        t=t%k++<1?          //     If `t` is divisible by `k`:
           0                //      Change `t` to 0
          :                 //     Else:
           t                //      Leave `t` as is
      );                    //    End of inner loop (3)
                            //    (`t` remained the same after loop 3? -> It's a prime)
                            //   End of inner loop (2) (implicit / single-line body)
                            //  And of loop (1) (implicit / single-line body)
  return r;                 //  Return the result-counter
}                           // End of method

new Integer(s.substring(0,i)+j+(i<l?s.substring(i+1):"") will result in these integers:

For 0-9: 1, 2, 3, 4, 5, 6, 7, 8, 9.
For 10: 10, 20, 30, 40, 50, 60, 70, 80, 90, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19.
For 11: 11, 21, 31, 41, 51, 61, 71, 81, 91, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19.
etc.

\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES7), 118 bytes

Takes input as a string.

n=>[...2**29+'4'].map(d=>n.replace(/./g,c=>s+=d+i>0&(P=k=>N%--k?P(k):N-n&&k==1)(N=p+d+n.slice(++i),p+=c),i=p=0),s=0)|s

Try it online!

Commented

n =>                        // n = input number (as a string)
  [...2**29 + '4']          // generate "5368709124" (all decimal digits)
  .map(d =>                 // for each digit d in the above string:
    n.replace(/./g, c =>    //   for each digit c in n:
      s +=                  //     increment s if the following code yields 1:
        d + i > 0 & (       //       if this is not the first digit of n or d is not "0":
          P = k =>          //         P = recursive function taking k and using N:
            N % --k ?       //           decrement k; if k is not a divisor of N:
              P(k)          //             do recursive calls until it is
            :               //           else:
              N - n &&      //             return true if N is not equal to n
              k == 1        //             and k is equal to 1 (i.e. N is prime)
          )(                //         initial call to P ...
            N =             //           ... with N defined as:
              p +           //             the current prefix p
              d +           //             followed by d
              n.slice(++i), //             followed by the trailing digits
                            //             (and increment the pointer i)
            p += c          //           append c to p
          ),                //         end of initial call
          i = p = 0         //         start with i = p = 0
    ),                      //   end of replace()
    s = 0                   //   start with s = 0
  ) | s                     // end of map(); return s
\$\endgroup\$
0
\$\begingroup\$

Ruby with -rprime, 101 bytes

-rprime imports the Prime module into Ruby. Get all primes up to \$10^{floor(log_{10} n)+1}\$ and count how many have the same number of digits from \$n\$ and are also 1 digit off.

->n{d=n.digits;Prime.each(10**l=d.size).count{|x|d.zip(e=x.digits).count{|a,b|a==b}==l-1&&e.size==l}}

Try it online!

\$\endgroup\$

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.