I ain't no Fortunate sum

Question

The primorial \$p_n\#\$ is the product of the first \$n\$ primes. The sequence begins \2,ドル 6, 30, 210, 2310\$.

A Fortunate number, \$F_n\$, is the smallest integer \$m > 1\$ such that \$p_n\# + m\$ is prime. For example \$F_7 = 19\$ as:

$$p_7\# = 2\times3\times5\times7\times11\times13\times17 = 510510$$

Adding each number between \2ドル\$ and \18ドル\$ to \510510ドル\$ all yield composite numbers. However, \510510ドル + 19 = 510529\$ which is prime.

The Fortunate numbers below \200ドル\$ are

$3,ドル 5, 7, 13, 17, 19, 23, 37, 47, 59, 61, 67, 71, 79, 89, 101, 103, 107, 109, 127, 151, 157, 163, 167, 191, 197, 199$$

We'll say an integer \$n\$ is a "Fortunate sum" if it can be expressed as the sum of two distinct Fortunate numbers. For example, \22ドル = 3 + 19 = 5 + 17\$, so \22ドル\$ can be expressed as the sum of two Fortunate numbers, and so is a "Fortunate sum"

You are to take an integer \$n\$ as input and output a truthy value if \$n\$ is a Fortunate sum and a falsey value otherwise. You may swap the order (falsey indicates it is a Fortunate sum) if you wish. You may take input and output in any convenient format.

This is code-golf so the shortest code in bytes wins

Test cases

The first line is the Fortunate sums less than 100 (truthy values) and the second are the integers less than or equal to 100 that aren't Fortunate sums

8 10 12 16 18 20 22 24 26 28 30 32 36 40 42 44 50 52 54 56 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98
1 2 3 4 5 6 7 9 11 13 14 15 17 19 21 23 25 27 29 31 33 34 35 37 38 39 41 43 45 46 47 48 49 51 53 55 57 58 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 100

• caird coinheringaahing: Brownie points for beating my 17 byte Jelly answer
• user100690: One of the greatest titles I've seen on PPCG...
• Luis Mendo: +1 for the musical reference
• Arnauld: Maybe it's worth noting that we don't necessarily have \$F_j>F_i\$ for \$j>i\$. So it is most probably be incorrect to just generate fortunate numbers from \$F_1\$ to some \$F_k>n\$ and look for a valid sum using only these values. It would be interesting to have an explicit test case where this method is known to fail.
• Manish Kundu: @Arnauld n=62 seems like such a case, it can only be formed using 3+59 and if you go in order you will encounter numbers upto 107 before getting 59. And the question already covers sums upto 100 so I think it's fine.

Answer 1

Haskell, ^{(削除) 130 (削除ここまで)} 128 bytes

a n=or[f x&&f(n-x)|x<-[2..n],2*x<n]
f m=or[and[p(x+y)/=(y<m)|y<-[2..m]]|x<-scanl1(*)$filter p[2..m]]
p n=all((>0).mod n)[2..n-1]

Try it online!

This solution is based on the following observation.

Fact. An integer \$m>1\$ is Fortunate if and only if, for some prime number \$p_n<m\$, \$m\$ is the smallest integer \$>1\$ such that \$ p_1 p_2\cdots p_n+m \$ is prime.

Proof. The claim follows easily from the fact that if \$p_n\ge m\$ then there is some \$p_i\$ with \$i\le n\$ such that \$p_i\mid m\$, and therefore \$p_i\mid p_1 p_2\cdots p_n+m\$.

At this point, checking if a number \$m\$ is Fortunate is trivial: we just have to check the condition for all the prime numbers up to \$m\$.

Explanation of the code

p n=all((>0).mod n)[2..n-1]

The standard prime-checking function. Only works for n>1, but that's ok.

---

f m=or[and[p(x+y)/=(y<m)|y<-[2..m]]|x<-scanl1(*)$filter p[2..m]]

A function to check whether a number m is Fortunate. As explained above, it calculates the primorials \$\texttt{x}=p_1p_2\cdots p_n\$ until \$p_n\le\texttt{m}\$ and tests whether m is the smallest integer \$\texttt{y}>1\$ such that \$\texttt{x}+\texttt{y}\$ is prime.

---

a n=or[f x&&f(n-x)|x<-[2..n],2*x<n]

The final function, to check whether n is a Fortunate sum. Pretty straightforward, the only thing to be careful of is that x and n-x must be different: this is the reason why we only iterate over values of x such that 2*x<n.

Answer 2

Wolfram Language (Mathematica), 106 bytes

Check[Tr[1^Union[#&@@IntegerPartitions[#,{2},Array[NextPrime[a=Times@@Array[Prime,#]+1]-a+1&,#]]]]>1,1>2]&

Try it online!

Answer 3

Jelly, (削除) 14 (削除ここまで) 13 bytes

-1 thanks to ChartZBelatedly! (use the built-in for choose-2.)

Thanks to Delfad0r for the simple explanation in their Haskell answer proving that this works, I probably would not have posted it otherwise!

ÆRPƤ‘Æn_ƊŒc§ċ

A monadic Link accepting an integer \$n\$ that yields a positive integer if \$n\$ is a Fortunate Sum, or zero if not.

Try it online! Or see A split of \$n\leq 100\$ into non-Fortunate and Fortunate Sums.

How?

ÆRPƤ‘Æn_ƊŒc§ċ - Link: integer, n e.g. 18
ÆR - primes between 2 and n inclusive [2,3, 5, 7, 11, 13, 17]
 Ƥ - for prefixes:
 P - product [2,6 ,30,210,2310,30030,510510]
 Ɗ - last three links as a monad, f(x=that):
 ‘ - increment (x) [3,7 ,31,211,2311,30031,510511]
 Æn - next, strictly greater, prime [5,11,37,223,2333,30047,510529]
 _ - subtract (x) [3,5, 7, 13, 23, 17, 19]
 Œc - choose-2 [[3,5],[3,7],[3,13],[3,23],[3,17],[3,19],[5,7],[5,13],[5,23],[5,17],[5,19],[7,13],[7,23],[7,17],[7,19],[13,23],[13,17],[13,19],[23,17],[23,19],[17,19]]
 § - sums [8,10,16,26,20,22,12,18,28,22,24,20,30,24,26,36,30,32,40,42,36]
 ċ - count occurrences (of n) 1 (truthy)

• caird coinheringaahing: œc2 can be Œc
• Jonathan Allan: Ah yeah, thanks for that @ChartZBelatedly!
• caird coinheringaahing: I lost the link to my 17 byte version, and I'm trying to remember how it wasn't this, because aside from me using ×\ instead of PƤ and i instead of ċ, this is exactly what I remember mine being :/
• Jonathan Allan: Odd, maybe you mistakenly counted what would be a footer to give either one or both of the two sets below 100?
• caird coinheringaahing: Quite possibly. Guess we'll never know though :/ +1 for outgolfing me :)

Answer 4

05AB1E, (削除) 35 (削除ここまで) (削除) 31 (削除ここまで) (削除) 29 (削除ここまで) 28 bytes

Lʒ©ÅPηPε2®Ÿ+pJΘ}à}ãʒË_}OI¢Íd

Try it online!

-4 bytes thanks to ovs

A port of Delfad0r's Haskell answer.

• ovs: I think OĀ can be à (maximum) for -1, Ùg< -> Ë_ (not all equal) and εO} -> €O.
• ovs: And the . in .¢ shouldn't be necessary, as we have a flat list in the end: Try it online!