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


Groups > comp.soft-sys.math.mathematica > #7805 > unrolled thread

Re: Solve stuck at 243

Started byAndrzej Kozlowski <akoz@mimuw.edu.pl>
First post2012-01-14 08:03 +0000
Last post2012-01-14 08:03 +0000
Articles 1 — 1 participant

Back to article view | Back to comp.soft-sys.math.mathematica

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.


Contents

  Re: Solve stuck at 243 Andrzej Kozlowski <akoz@mimuw.edu.pl> - 2012-01-14 08:03 +0000

#7805 — Re: Solve stuck at 243

FromAndrzej Kozlowski <akoz@mimuw.edu.pl>
Date2012-01-14 08:03 +0000
SubjectRe: Solve stuck at 243
Message-ID<jercrn$1fk$1@smc.vnet.net>
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
>

[toc] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web