6
\$\begingroup\$

A Woodall Prime is a prime which can be calculated, given a positive integer n, with n * 2^n - 1.

Your task is to, given a integer k, generate a Woodall Prime with k digits. If no such Woodall Prime exists, you must generate a Woodall Prime with the closest amount of digits. If two primes exist with the same digit count difference, you may use either.

You may assume that there exists no two Woodall Primes with the same amount of digits.

There is no time complexity limit, and you must be able to handle at least the first ten Woodall Primes (you can see them in the OEIS link at the start of the question)

You may write a full program or a function, and you may print or return the output.

Examples:

1 -> 7
4 -> 383
0 -> 7
-100 -> 7
7 -> 383 or 32212254719 (you may pick either of these)
8 -> 32212254719

As this is , that shortest code wins!

(there are only nine Woodall Primes on the linked OEIS sequence, so you might want to look at this for more Woodall Primes: https://oeis.org/A002234)

\$\endgroup\$
  • 1
    \$\begingroup\$ Handling negative input seems like a excess requirement, if the input is supposed to be how many digits the output should be. What even does -100 digits mean? \$\endgroup\$ – AdmBorkBork Feb 15 '17 at 17:31
  • \$\begingroup\$ @AdmBorkBork 1 digit is closest to -100 digits. -100 digits isn't possible, and the question asks for the Woodall Prime with the closest amount of digits. \$\endgroup\$ – Okx Feb 15 '17 at 17:34
  • 13
    \$\begingroup\$ Someone watched numberphile today. :) \$\endgroup\$ – Martin Ender Feb 15 '17 at 17:36
  • 1
    \$\begingroup\$ @Okx it's not obvious, which is why I asked. Your example says the output for 7 is 383 or 32212254719 someone may take that literally, you should change it to 383 or 32212254719 (pick one). \$\endgroup\$ – Magic Octopus Urn Feb 15 '17 at 17:47
  • 1
    \$\begingroup\$ Jesus, I am absolutely NOTORIOUS for missing text bits inside of questions, sorry for coming off rude. I didn't see the snippet about either near the top. \$\endgroup\$ – Magic Octopus Urn Feb 15 '17 at 17:53
3
\$\begingroup\$

Brachylog, 28 26 bytes

:K≜+ℕ~lṗ.+₁~×[İ,J]h:2^₍J≜∧

Try it online!

This is too slow for TIO for inputs bigger than 4.

Explanation

:K                             The list [Input, K]
  ≜                            Assign a value to K (0, then 1, then -1, then 2, etc.)
   +ℕ                          Input + K >= 0
     ~l .                      Output is a number of length (Input + K)
       ṗ.                      Output must be a prime number
         +₁                    Output + 1...
           ~×[İ,J]             ... = İ × J, İ being an integer...
                  h:2^₍J       ... and J = 2^İ
                         ≜∧    Check that it is possible to find a value for İ that satisfies
                                 all of those constraints. If not, go back to the beginning
                                 and try another value for K through backtracking.

We use a common trick in Brachylog for "find the closest X to Y": labeling a completely free variable (which we do when we use on the list [Input, K] will label it with this pattern: 0, 1, -1, 2, -2, 3, .... Therefore, when backtracking if the value Input + K doesn't work as the number of digits, the next choice we will try will be the next possible closest choice.

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

Mathematica, 72 bytes

Nearest@<|Thread[w->IntegerLength[w=# 2^#-1&~Array~999~Select~PrimeQ]]|>

Pure function taking an integer as input and returning the set of Woodall primes whose lengths are closest to the input. For example, applying this function to 6 results in {383}, while applying it to 7 yields }{383,32212254719}.

w=# 2^#-1&~Array~999~Select~PrimeQ constructs a list of the first 15 Woodall primes, by testing all numbers of the form n*2^n-1 with n up to 999. <|Thread[w->IntegerLength[w]]|> creates an association taking the number of digits of each of these Woodall primes to the primes themselves. Then Nearest picks out the Woodall primes whose numbers-of-digits are closest to the input.

\$\endgroup\$
0
\$\begingroup\$

Perl 6,  71  68 bytes

->\k{({$/ if is-prime $/=2**++$*++$-1}...*.chars>k).min:{abs k-.chars}}

Try it

{({$/ if is-prime $/=2**++$*++$-1}...*.comb>$^k).min:{abs $k-.comb}}

Try it

Expanded:

{         # bare block lambda with parameter 「$k」
  (  # sequence of possible candidates

    {
      $/         # use the Woodall number
      if         # but only if
      is-prime(  # this is prime

        $/ =     # store the Woodall number in $/

         2 **    # 2 to the power of
         ++$     # n           ( preincrement of anon state variable )
         *       # times
         ++$     # n           ( preincrement of anon state variable )
         -1      # -1

      )
    }

    ...          # keep generating Woodall primes until:

    *.comb > $^k  # it has more digits than 「$k」 (declare 「$k」 as a parameter)

  ).min: { abs $k - .comb } # find the nearest one
}
\$\endgroup\$

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.