Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #7786

Re: Solve stuck at 243

From Ralph Dratman <ralph.dratman@gmail.com>
Newsgroups comp.soft-sys.math.mathematica
Subject Re: Solve stuck at 243
Date 2012-01-14 07:52 +0000
Organization Steven M. Christensen and Associates, Inc and MathTensor, Inc.
Message-ID <jerc8h$174$1@smc.vnet.net> (permalink)
References <201201130953.EAA16531@smc.vnet.net>

Show all headers | View raw


Thank you, but I am actually not trying to solve the problem. I just
want to understand what happened to Solve and Prime.

Ralph

On Fri, Jan 13, 2012 at 8:11 AM, Andrzej Kozlowski <akoz@mimuw.edu.pl> wrote:
> I am not sure what happens there but the problem seems not difficult. Let's first define a fast function that checks if a number is a perfect square:
>
> perfectSquare =
>  Compile[{{x, _Integer}}, Module[{w = N[Sqrt[x]]}, w == Round[w]],
>  RuntimeAttributes -> {Listable}, Parallelization -> True]
>
> (I haven't really tested if this is the fastest way do to that, but it should be pretty fast. Of course it's not guaranteed to be correct for extremly large numbers but we hope they won't be needed). So now we define our test:
>
> test[n_] := Or @@ perfectSquare[(n - Prime[Range[2, PrimePi[n]]])/2]
>
> In other words, we look at the differences between a number and all the primes less than the number (excluding 2, of course), divide by two and check if there are any perfect squares. If there aren't, we have our solution.
>
> Catch[
>  Do[If[Not[PrimeQ[i]] && Not[test[i]], Throw[i]], {i, 9, 10^4, 2}]]
>
> 5777
>
> This is not as large as I had feared. We can actually confirm the computation exactly.
>
> Select[
>  Sqrt[With[{n = 5777}, (n - Prime[Range[2, PrimePi[n]]])/2]], IntegerQ]
>
> {}
>
>
> Andrzej Kozlowski
>
>
> On 13 Jan 2012, at 10:53, Ralph Dratman wrote:
>
>> Project Euclid asks, "What is the smallest odd composite
>> that cannot be written as the sum of a prime and twice a
>> square?"
>>
>> I tried the following equation, not really expecting it to
>> work:
>>
>> oddComposite == Prime[m] + 2 k^2
>>
>> Surprisingly, the above actually does work for all the odd
>> composite numbers through 237.
>>
>> solveInstance[oddComposite_] := Solve[{oddComposite ==
>> Prime[m] + 2*k^2, k > 0, m > 0}, {k, m}, Integers];
>> For[i = 9, i < 300, i = i + 2,
>> If[Not[PrimeQ[i]], Print[i,": ", solveInstance[i]]]]
>>
>> 9: {{k->1,m->4}}
>> 15: {{k->1,m->6},{k->2,m->4}}
>> 21: {{k->1,m->8},{k->2,m->6},{k->3,m->2}}
>> 25: {{k->1,m->9},{k->2,m->7},{k->3,m->4}}
>> 27: {{k->2,m->8}}
>> 33: {{k->1,m->11}}
>> 35: {{k->3,m->7},{k->4,m->2}}
>> 39: {{k->1,m->12},{k->2,m->11},{k->4,m->4}}
>> 45: {{k->1,m->14},{k->2,m->12},{k->4,m->6}}
>> 49: {{k->1,m->15},{k->2,m->13},{k->3,m->11},{k->4,m->7}}
>> 51: {{k->2,m->14},{k->4,m->8}}
>>
>> - - - - - - snip - - - - - -
>>
>> 217: {{k->3,m->46},{k->5,m->39},{k->8,m->24},{k->10,m->7}}
>> 219: {{k->2,m->47},{k->10,m->8}}
>> 221: {{k->6,m->35},{k->9,m->17}}
>> 225: {{k->1,m->48},{k->4,m->44},{k->7,m->31},{k->8,m->25}}
>> 231:
>> {{k->1,m->50},{k->2,m->48},{k->4,m->46},{k->5,m->42},{k->8,m
>> ->27},{k->10,m->11}}
>> 235:
>> {{k->1,m->51},{k->2,m->49},{k->6,m->38},{k->7,m->33},{k->8,m
>> ->28},{k->9,m->21}}
>> 237: {{k->2,m->50},{k->7,m->34},{k->8,m->29},{k->10,m->12}}
>>
>> - - - - - - but then, at 243, something changes - - - - -
>>
>> 243: {{k->1,m->53},{k->4,m->47},{k->5,m->44},{k->10,m->14}}
>> Solve::nsmet: This system cannot be solved with the methods
>> available to Solve. >>
>>
>> 245: Solve[{245==2 k^2+Prime[m],k>0,m>0},{k,m},Integers]
>> Solve::nsmet: This system cannot be solved with the methods
>> available to Solve. >>
>>
>> 247: Solve[{247==2 k^2+Prime[m],k>0,m>0},{k,m},Integers]
>> Solve::nsmet: This system cannot be solved with the methods
>> available to Solve. >>
>>
>> ... and so on. Strange.
>>
>> Does anyone know why such a threshold might appear?
>>
>> Thank you.
>>
>> Ralph Dratman
>>
>

Back to comp.soft-sys.math.mathematica | Previous | Next | Find similar | Unroll thread


Thread

Re: Solve stuck at 243 Ralph Dratman <ralph.dratman@gmail.com> - 2012-01-14 07:52 +0000

csiph-web