12
\$\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.

Let us generalise this to integer sequences beyond primes however. Let \$\Pi(S,n)\$ represent the product of the first \$n\$ elements of some infinite sequence \$S\$. All elements of \$S\$ are natural numbers (not including zero) and no element is repeated. \$S\$ is guaranteed to be strictly increasing.

In this case, \$p_n\# = \Pi(\mathbb P,n)\$. We can then define a new type of numbers, generalised Fortunate numbers, \$F(S,n)\$ as the smallest integer \$m > 1\$ such that \$\Pi(S,n) + m \in S\$.

You are to take an integer \$n\$ and an infinite sequence of positive integers \$S\$ and output \$F(S,n)\$.

You may take input in any reasonable representation of an infinite sequence. That includes, but is not limited to:

  • An infinite list, if your language is capable of handling those (e.g. Haskell)
  • A black box function which returns the next element of the sequence each time it is queried
  • A black box function which returns two distinct values to indict whether it's argument is a member of that sequence or not
  • A black box function which takes an integer \$x\$ and returns the \$x\$th element of the sequence

If you have another method you are considering using, please ask in the comments about it's validity.

This is so the shortest code in bytes wins

Examples

I'll walk through a couple of examples, then present a list of test cases below.

\$n = 5, S = \{1, 2, 6, 24, 120, ...\}\$

Here, \$S\$ is the factorials from 1. First, \$\Pi(S, 5) = 1\times2\times6\times24\times120 = 34560\$. We then find the next factorial greater than \$34560\$, which is \$8! = 40320\$ and subtract the two to get \$m = 40320 - 34560 = 5760\$.

\$n = 3, S = \{6, 28, 496, 8128, ...\}\$

Here, \$S\$ is the set of perfect numbers. First, \$\Pi(S, 3) = 6\times28\times496 = 83328\$. The next perfect number is \$33550336\$, so \$m = 33550336 - 83328 = 33467008\$

Test cases

n
S
F(S, n)

5
{1,2,6,24,120,...} (factorials)
5760

3
{6,28,496,8128,...} (perfect numbers)
33467008

7
{2,3,5,7,11,...} (prime numbers)
19

5
{1,3,6,10,15,...} (triangular numbers)
75

Any n
{1,2,3,4,...} (positive integers)
2

9
{1,4,9,16,25,...} (squares)
725761

13
{4,6,9,10,14,...} (semiprimes)
23
\$\endgroup\$
0

7 Answers 7

6
\$\begingroup\$

Husk, 8 bytes

ḟ>1M<¹Π↑

Try it online! (Missing the testcase for perfect numbers because it was too slow, and the one for semiprimes because implementing the list of semiprimes is a challenge itself)

Takes as input S and n, where S is an infinite list.

Explanation

ḟ>1M<¹Π↑
       ↑     Take the first n elements from S
      Π       and get their product
   M ¹       For each element x in S
    <         subtract the product if it is smaller than x, return 0 if it is bigger
ḟ            Find the first element in this list
 >1           that is greater than 1
\$\endgroup\$
2
\$\begingroup\$

JavaScript (V8), 70 bytes

n=>s=>{p=[...Array(n)].reduce(a=>a*s(),1);while((x=s()-p)<1);return x}

Can't access TIO on my school network. I'll post a link soon!

\$\endgroup\$
2
\$\begingroup\$

Scala, 83 bytes

s=>n=>{val p=s.take(n).product;Stream.from(2)find(m=>s takeWhile(p+m>=_)toSet p+m)}

Try it in Scastie!

Takes an infinite LazyList.

If outputting the product + m had been allowed, I could've used a few evil syntax-bending tricks for 71 bytes, but this is a lot more boring.

s=>Stream.from(2)map s.take(_).product.+find(? =>s takeWhile?.>=toSet?)

Try it in Scastie!

\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 47 bytes

(S,x=1)=>f=n=>n?f(n-1,x*=S()):(t=S()-x)>0?t:f()

Try it online!

JavaScript (Node.js), 51 bytes non-recursive

S=>n=>{for(x=1;e=S(),e<=(x*=n--<1||e););return e-x}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Clojure, 58 bytes

#(nth(for[i % j[(- i(apply *(take %2%)))]:when(< 1 j)]j)0)

Try it online!

Takes input as a lazy sequence and a number \$n\$.

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

J, 36 bytes

1 :'([(-~u)>:@]^:(>:u)^:_)~[:*/u@i.'

Try it online!

This is an adverb modifying the sequence generator, which is assumed to be 0-indexed and which returns the nth element.

It just increments the input n until f(n) > relevant product to find the number to subtract from.

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

05AB1E, 7 bytes

£P-.Δ1›

First input is \$n\$, second input is an infinite sequence \$S\$.

Verify all test cases or try it online with 05AB1E code as additional input to generate the infinite sequence. (The perfect numbers and semiprimes test cases have been lowered to \$n=2\$ and \$n=4\$ respectively, because they time out for \$n=3\$ and \$n=13\$ on TIO.)

Explanation:

£        # Leave the first (implicit) input `n` amount of leading items from the second
         # infinite input-list `S`
 P       # Take the product of these first `n` values
  -      # Subtract it from each item in the second infinite input-list `S`
   .Δ    # Pop and leave the first value which is truthy for:
     1›  #  Check that it's larger than 1
         # (after which the result is output implicitly)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.