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.
4I'm trying to think of the smallest
n
for which the output is0
. I think it'sn = 200
. I also think they come in bunches:200,202,204,206,208
,320,322,...,328
,510,...,518
,620,...628
,840,...,848
, etc. – Engineer Toast – 2017-08-02T16:24:25.777Does "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? – Dead Possum – 2017-08-02T16:39:08.050
1@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. – AdmBorkBork – 2017-08-02T16:41:50.200
Do let me know if I'm going overboard... I have 3 different submissions now – Patrick Roberts – 2017-08-02T21:41:36.097
@EngineerToast The bunches happen because a number
>7
ending in one of0,2,4,5,6,8
cannot be prime. However it might be possible to have a single prime number that still gives output 0, and has no such bunch because that prime itself gives 1 for the others. However, I tried searching (rather inefficiently) up to 99999 and didn't find any. – Ørjan Johansen – 2017-08-03T01:45:16.343@ØrjanJohansen I just searched for when the list of primes skipped over an entire range
10n
to10(n+1)
and then picked every even within that range. Picking the even values forces you to change just the ones digit since leaving it guarantees the result won't be prime. Anything you could change it to won't be prime, either, since there's no other prime in those ten numbers. – Engineer Toast – 2017-08-03T12:17:08.300+1 for the title (and the excellent challenge as well of course). – Kevin Cruijssen – 2017-08-03T14:38:39.313
@EngineerToast You can also include the number ending in 5. What I'm saying is that there could be a number with output 0 not of that type, if we're extremely lucky. (It seems hard to avoid hitting other primes, but only for statistical reasons.) – Ørjan Johansen – 2017-08-04T01:29:20.270
2
@EngineerToast After finding the first example prime (294001), I finally thought of looking it up on OEIS: A192545 and A158124. Also relevant: A143641.
– Ørjan Johansen – 2017-08-04T17:17:53.153@ØrjanJohansen It's too bad we can't give bounties for comments. That's great work! – Engineer Toast – 2017-08-04T18:57:33.150