13
\$\begingroup\$

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 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
\$\endgroup\$
8
  • 1
    \$\begingroup\$ Brownie points for beating my 17 byte Jelly answer \$\endgroup\$ Mar 15, 2021 at 17:04
  • 5
    \$\begingroup\$ One of the greatest titles I've seen on PPCG... \$\endgroup\$
    – user100690
    Mar 15, 2021 at 17:07
  • 5
    \$\begingroup\$ +1 for the musical reference \$\endgroup\$
    – Luis Mendo
    Mar 15, 2021 at 17:26
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Arnauld
    Mar 15, 2021 at 17:37
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ Mar 15, 2021 at 17:59

4 Answers 4

7
\$\begingroup\$

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.

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

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!

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

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)
\$\endgroup\$
5
  • 1
    \$\begingroup\$ œc2 can be Œc \$\endgroup\$ Mar 16, 2021 at 21:18
  • \$\begingroup\$ Ah yeah, thanks for that @ChartZBelatedly! \$\endgroup\$ Mar 16, 2021 at 21:19
  • \$\begingroup\$ 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 and i instead of ċ, this is exactly what I remember mine being :/ \$\endgroup\$ Mar 16, 2021 at 21:29
  • \$\begingroup\$ Odd, maybe you mistakenly counted what would be a footer to give either one or both of the two sets below 100? \$\endgroup\$ Mar 16, 2021 at 21:31
  • \$\begingroup\$ Quite possibly. Guess we'll never know though :/ +1 for outgolfing me :) \$\endgroup\$ Mar 16, 2021 at 21:33
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I think can be à (maximum) for -1, Ùg< -> Ë_ (not all equal) and εO} -> €O. \$\endgroup\$
    – ovs
    Mar 16, 2021 at 12:01
  • \$\begingroup\$ And the . in shouldn't be necessary, as we have a flat list in the end: Try it online! \$\endgroup\$
    – ovs
    Mar 16, 2021 at 12:08

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.