4
$\begingroup$

For every prime number $p$, the function ${\rm ms_2}(p)$ gives the smallest prime number that results in a power of 2 when added to $p$.

For example: ${\rm ms_2}(857) = 167$, since $857+167 = 1024 = 2^{10}$.

What is wrong with this Mathematica code?

ms2[n_] := Module[{p}, Do[If[PrimeQ[p = NextPrime[n]] && 2^n - p == 1, Return[p]], {p, n + 1}]] ##
Improve this question
$\endgroup$
1
  • $\begingroup$ For one thing, you seem to have p ranging from 1 to n+1 from the Do, but are also trying to assign p to be NextPrime[n] (which will never change). You probably don't want both of those. $\endgroup$ Commented Jul 21, 2023 at 18:46

3 Answers 3

Reset to default
3
$\begingroup$

Another implementation using NestWhile:

f[p_]:=NestWhile[2 # &, 2^Ceiling[Log[2, p]], !PrimeQ[# - p] &] - p; f[857] f[859] (*167*) (*7333*)

Some primes have crazy large values:

plotData = Table[{i, f[i]}, {i, Prime[Range[285]]}]; ListLinePlot[plotData, PlotRange -> All, ScalingFunctions -> "Log"]

enter image description here

In fact, some are so large I haven't even gotten an answer: f[1871] just runs indefinitely.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you Ydd. One question: does your implementation consider 1 as a prime number? Because f[7]=1 and not the correct answer f[7]=549755813881 (7+549755813881=2^39). I appreciate the clarification. $\endgroup$ Commented Jul 22, 2023 at 11:28
  • $\begingroup$ @RubensVilhenaFonseca thanks for pointing this out. This arose from the fact I was checking at each nest level if CompositeQ[# - p] & and since 1 is neither composite nor prime, it would stop if the difference was 1. I changed it to !PrimeQ[# - p]& so this should only stop if the difference is Prime (which 1 is not). Apologies for that. $\endgroup$ Commented Jul 22, 2023 at 15:33
  • $\begingroup$ @RubensVilhenaFonseca there was also some issue with my plot where it wasn't actually plotting the values of f. I fixed my plot and you can see there are some primes where the value is so large it drowns out everything else in the plot, even in log scale! $\endgroup$ Commented Jul 22, 2023 at 15:53
  • $\begingroup$ ydd, thank you very much for your corrections. $\endgroup$ Commented Jul 22, 2023 at 16:54
2
$\begingroup$

Why not NestWhile

f[n_] := NestWhile[NextPrime, 0, !IntegerQ[Log2[ # + n]]& ]; f[859]

7333

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you AsukaMinato. Would you know how long on average your implementation would take to give the answer for f[7]? $\endgroup$ Commented Jul 22, 2023 at 11:32
1
$\begingroup$

It's hard to pinpoint exactly what is wrong because there are several weird things about your code and how you use variables.

Anyhow, keeping the same algorithmic approach, one could use While loop:

ms2[n_] := Module[{p = 1}, While[p = NextPrime[p]; ! IntegerQ[Log2[n + p]]]; p]; ms2[857] (* 167 *)
Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.