8
\$\begingroup\$

This challenge was originally posted on codidact.


Given a number \$n \geq 3\$ as input output the smallest number \$k\$ such that the modular residues of \$k\$ by the first \$n\$ primes is exactly \$\{-1,0,1\}\$.

That is, there are three primes in the first \$n\$ primes, so that prime 1 divides \$k\$, prime 2 divides \$k+1\$ and prime 3 divides \$k-1\$, and every prime in the first \$n\$ primes divides one of those three values.

For example if \$n=5\$, the first \$5\$ primes are \$2, 3, 5, 7, 11\$ the value must be at least \$10\$ since with anything smaller \$11\$ is an issue. So we start with \$10\$:

$$ 10 \equiv 0 \mod 2 $$ $$ 10 \equiv 1 \mod 3 $$ $$ 10 \equiv 0 \mod 5 $$ $$ 10 \equiv 3 \mod 7 $$

Since \$10 \mod 7 \equiv 3\$, \$10\$ is not a solution so we try the next number.

  • \$11 \equiv 4\mod 7\$ so we try the next number.
  • \$12 \equiv 2\mod 5\$, so we try the next number.
  • \$13 \equiv 3\mod 5\$, so we try the next number.
  • \$14 \equiv 3\mod 11\$, so we try the next number.
  • \$15 \equiv 4\mod 11\$, so we try the next number.
  • \$16 \equiv 2\mod 7\$, so we try the next number.
  • \$17 \equiv 2\mod 5\$, so we try the next number.
  • \$18 \equiv 3\mod 5\$, so we try the next number.
  • \$19 \equiv 5\mod 7\$, so we try the next number.
  • \$20 \equiv 9\mod 11\$, so we try the next number.

$$ 21 \equiv 1 \mod 2 $$ $$ 21 \equiv 0 \mod 3 $$ $$ 21 \equiv 1 \mod 5 $$ $$ 21 \equiv 0 \mod 7 $$ $$ 21 \equiv -1 \mod 11 $$

21 satisfies the property so its the answer.

Task

Take as input \$n \geq 3\$ and give as output the smallest number satisfying.

This is . The goal is to minimize the size of your source code as measured in bytes

Test cases

3 -> 4
4 -> 6
5 -> 21
6 -> 155
7 -> 441
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Is there any difference with A080611? The fact that the set must be exactly \$\{-1,0,1\}\$ puzzles me. \$\endgroup\$
    – Arnauld
    Aug 5, 2023 at 14:35
  • 1
    \$\begingroup\$ @Arnauld I had conjectured they were the same, it is hard to prove however. \$\endgroup\$
    – Wheat Wizard
    Aug 5, 2023 at 17:06
  • \$\begingroup\$ Does an odd number count as +1 and -1 mod 2? \$\endgroup\$
    – loopy walt
    Aug 6, 2023 at 3:57
  • \$\begingroup\$ @loopywalt I've updated the question. It can count as either or. \$\endgroup\$
    – Wheat Wizard
    Aug 6, 2023 at 11:10

8 Answers 8

4
\$\begingroup\$

Charcoal, 32 bytes

Nθ→W‹Lυθ«→¿⬤υ﹪ⅈκ⊞υⅈ»W›⌈﹪ⅈυ²M→I⊖ⅈ

Try it online! Link is to verbose version of code. Explanation: Port of @UnrelatedString's Jelly answer.

Nθ

Input n.

→W‹Lυθ«→¿⬤υ﹪ⅈκ⊞υⅈ»

Generate the first n primes.

W›⌈﹪ⅈυ²M→

Continue counting up while the number's greatest residue modulo those n primes exceeds 2.

I⊖ⅈ

Decrement to produce the final result.

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

Jelly, 11 bytes

%Ṁ=2ʋ1#ÆN€’

Try it online!

     1#        Find the first integer starting from n for which
 Ṁ             its greatest
%   ʋ  ÆN€     residue modulo the first n primes
  =2           is 2.
          ’    Decrement.

If \$k\$ has residues \$ \{-1,0,1\} \$, \$k + 1\$ has residues \$\{0, 1, 2\}\$. On reflection, I'm... not entirely sure this program is valid, since 1. it might erroneously reject a \$k\$ with its only \$1\$ residue from \$2\$, and 2. while every integer necessarily has \$0\$ and \$1\$ as residues from some primes, it's not clear that there's no \$n\$ for which some erroneous \$k\$ with a maximum minimal-positive residue of \$2\$ mod the first \$n\$ primes but not \$0\$ and \$1\$ mod one of the first \$n\$ primes is less than the real least \$k\$. However, it does pass the test cases, and it seems plausible that it is in fact correct.

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

Vyxal G, 80 bitsv2, 10 bytes

?ʁǎ%G2=)2ȯ‹

Try it Online!

A little goofy port of Jelly.

Explained

?ʁǎ%G2=)2ȯ‹­⁡​‎‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁢⁣​‎‏​⁢⁠⁡‌­
       )2ȯ   # ‎⁡First two integers where
    G        # ‎⁢  The maximum of
?ʁǎ%         # ‎⁣  [k % x for x in first n primes]
     2=      # ‎⁤  Equals 2
        2ȯ   # ‎⁢⁡The first two integers is because 1 is considered to pass the test, meaning that it needs to be accounted for. This could otherwise just be a single byte if there was something that started from n
          ‹  # ‎⁢⁢Decrement
# ‎⁢⁣The G flag gets the biggest item (which is the number in the list that _isn't_ 1)
💎

Created with the help of Luminespire.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ What makes you unsure? \$\endgroup\$
    – Wheat Wizard
    Aug 5, 2023 at 12:56
  • \$\begingroup\$ Just whether I've understood the question correctly \$\endgroup\$
    – lyxal
    Aug 5, 2023 at 12:58
2
\$\begingroup\$

Thunno 2 t, 12 bytes

2Ƙ$LÆP%G2=;⁻

Try it online!

Port of Unrelated String's Jelly answer.

Explanation

2Ƙ$LÆP%G2=;⁻  # Implicit input
2Ƙ        ;   # First 2 positive integers where:
  $LÆP        #   List of the first (input) primes
      %       #   The current number mod this
       G2=    #   Maximum equals 2
           ⁻  # Decrement both
              # Implicit output of last item
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 95 bytes

f=(n,k)=>(y=L=[],g=n=>(P=i=>y%i--?P(i):i)(y++)?n&&g(n):L[-~k%y]=g(n-1))(n)+',0,0'==L?k:f(n,-~k)

Try it online!

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

Python 2, 115 bytes

f=lambda n,i=1,p=1:n*[0]and p%i*[i]+f(n-p%i,i+1,p*i*i)
x=3;q=f(input())
while max(x%y for y in q)>2:x+=1
print(x-1)

Try it online!

Uses Lynn's function to get the first n primes. Port of Unrelated String's Jelly answer.

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

Retina, 89 bytes

r`\d*$
¶__
"$&"}+`\b(_+)(¶_+)*¶\1+$
$&_
$
¶$%`
+`(?>\b(_+)(¶_+)*¶\1*)(?!_?_?$)
$&_
G`$
\B

Try it online! Link includes test cases. Explanation:

r`\d*$
¶__

Append 2 in unary to the buffer, deleting any input number. This awkward approach is fortunately the same length as the more straightforward approach of deleting the input number before starting the loop, as that version then requires history, which prevents more than one test case from being run at once.

\b(_+)(¶_+)*¶\1+$
$&_

If the last value in the buffer is divisible by any of the previous values then increment it.

+`

Repeat until it becomes prime.

"$&"}`

Repeat until n primes have been generated.

$
¶$%`

Make a copy of the nth prime.

(?>\b(_+)(¶_+)*¶\1*)(?!_?_?$)
$&_

If there is a prime for which the copy does not have a residue of no more than 2 then increment it. The atomic group (?>...) ensures that the regex doesn't try to add the prime to the residue to increase it to more than 2, or worse, divide one of the primes by one of the other primes.

+`

Repeat until no residue is greater than 2.

G`$

Keep only the final result.

\B

Subtract 1 and convert it to decimal.

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

05AB1E, 11 bytes

∞+.Δ>IÅp%à<

Port of @UnrelatedString's Jelly answer.

Try it online or verify all test cases.

Explanation:

∞            # Push an infinite positive list: [1,2,3,...]
 +           # Add the (implicit) input-integer to each: [n+1,n+2,n+3,...]
  .Δ         # Find the first integer that's truthy for:
    >        #  Increase the current value by 1: [n+2,n+3,n+4,...]
     IÅp     #  Push a list of the first input amount of primes
        %    #  Modulo the current value+1 by each of these primes
         à   #  Pop and push the maximum remainder
          <  #  Verify that it's equal to 2, by decreasing it by 1 (since only 1 is
             #  truthy in 05AB1E)
             # (after which the found 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.