Unsolved Problems (Not Independent of ZFC) due to Lack of Computational PowerIs there any conjecture that we...

Potential new partner angry about first collaboration - how to answer email to close up this encounter in a graceful manner

Shouldn't the "credit score" prevent Americans from going deeper and deeper into personal debt?

Three Singles in Three Clubs

Why did MS-DOS applications built using Turbo Pascal fail to start with a division by zero error on faster systems?

In the MCU, why does Mjölnir retain its enchantments after Ragnarok?

Fried gnocchi with spinach, bacon, cream sauce in a single pan

How much code would a codegolf golf if a codegolf could golf code?

Is there a known non-euclidean geometry where two concentric circles of different radii can intersect? (as in the novel "The Universe Between")

How do I make distance between concentric circles equal?

If all stars rotate, why was there a theory developed, that requires non-rotating stars?

Why is 日本 read as "nihon" but not "nitsuhon"?

Sleeping solo in a double sleeping bag

If the first law of thermodynamics ensures conservation of energy, why does it allow systems to lose energy?

What professions would a medieval village with a population of 100 need?

Why is my Earth simulation slower than the reality?

LeetCode: Pascal's Triangle C#

Why don't electrons take the shorter path in coils

Why didn’t Doctor Strange stay in the original winning timeline?

The teacher logged me in as administrator for doing a short task, is the whole system now compromised?

Script that helps people make better choices

Concatenation of the result of a function with a mutable default argument in python

In an emergency, how do I find and share my position?

Fancy String Replace

Most practical knots for hitching a line to an object while keeping the bitter end as tight as possible, without sag?



Unsolved Problems (Not Independent of ZFC) due to Lack of Computational Power


Is there any conjecture that we know is provable/disprovable but we haven't found a proof of yet?How to show $e^{e^{e^{79}}}$ is not an integer$e^{e^{e^{79}}}$ and ultrafinitismTheorems true “with probability 1”?Can all maths be represented in geometry?Examples of falsified (or currently open) longstanding conjectures leading to large bodies of incorrect results.Big-Daddy-Conjectures and Hierarchy of Mathematical ConjecturesFormal notion of computational contentFirst job in industry for a pure, pure mathematics folkAlgorithmic procedure to establish the possibility of finding a proof of a conjenctureHow to know if one problem is more difficult than another one?






.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}







49












$begingroup$


I was recently reading up about computational power and its uses in maths particularly to find counterexamples to conjectures. I was wondering are there any current mathematical problems which we are unable to solve due to our lack of computational power or inaccessibility to it.



What exactly am I looking for?



Problems of which we know that they can be solved with a finite (but very long) computation?



(e. g. NOT the Riemann hypothesis or twin prime conjecture)



FROM THE COMMENTS



(Maybe this will be helpful for people to understand the question in a better way if they don't already.)



There is a simple algorithm which simply lists all statements provable in
ZFC, so with sufficient computational power you could prove anything that's provable. However, something like the Riemann hypothesis can't necessarily be resolved this way, since it might be independent from ZFC, in which case neither it nor its negation will ever be proven by the program. Indeed, the class of unsolved problems I AM interested in is precisely the class of open problems which are known to not be independent from ZFC.



I am looking for specific examples.










share|cite|improve this question











$endgroup$










  • 2




    $begingroup$
    What exactly are you looking for? Problems of which we know that they can be solved with a finite (but very long) computation? (e. g. not the Riemann hypothesis or twin prime conjecture)
    $endgroup$
    – 0x539
    Aug 16 at 20:49






  • 6




    $begingroup$
    Near duplicate on MO mathoverflow.net/q/112097/30186
    $endgroup$
    – Wojowu
    Aug 17 at 9:39






  • 4




    $begingroup$
    Perhaps Skewes' number, the least $x$ for which $pi(x)le li(x)$.
    $endgroup$
    – DanielWainfleet
    Aug 17 at 11:47






  • 3




    $begingroup$
    The first thing I thought of is chess — 8-piece tablebases are currently on the bubble, and position counts at ply N are only up to N=13 or something — but not sure that’s “math” by your definition.
    $endgroup$
    – Jeff Y
    Aug 17 at 12:42






  • 3




    $begingroup$
    As @MarcGlisse mentions, there is a simple algorithm which simply lists all statements provable in ZFC, so with sufficient computational power you could prove anything that's provable. However, something like the Riemann hypothesis can't necessarily be resolved this way, since it might be independent from ZFC, in which case neither it nor its negation will ever be proven by the program. Indeed, the class of unsolved problems the OP is interested in is precisely the class of open problems which are known to not be independent from ZFC.
    $endgroup$
    – Jim Belk
    Aug 18 at 9:12




















49












$begingroup$


I was recently reading up about computational power and its uses in maths particularly to find counterexamples to conjectures. I was wondering are there any current mathematical problems which we are unable to solve due to our lack of computational power or inaccessibility to it.



What exactly am I looking for?



Problems of which we know that they can be solved with a finite (but very long) computation?



(e. g. NOT the Riemann hypothesis or twin prime conjecture)



FROM THE COMMENTS



(Maybe this will be helpful for people to understand the question in a better way if they don't already.)



There is a simple algorithm which simply lists all statements provable in
ZFC, so with sufficient computational power you could prove anything that's provable. However, something like the Riemann hypothesis can't necessarily be resolved this way, since it might be independent from ZFC, in which case neither it nor its negation will ever be proven by the program. Indeed, the class of unsolved problems I AM interested in is precisely the class of open problems which are known to not be independent from ZFC.



I am looking for specific examples.










share|cite|improve this question











$endgroup$










  • 2




    $begingroup$
    What exactly are you looking for? Problems of which we know that they can be solved with a finite (but very long) computation? (e. g. not the Riemann hypothesis or twin prime conjecture)
    $endgroup$
    – 0x539
    Aug 16 at 20:49






  • 6




    $begingroup$
    Near duplicate on MO mathoverflow.net/q/112097/30186
    $endgroup$
    – Wojowu
    Aug 17 at 9:39






  • 4




    $begingroup$
    Perhaps Skewes' number, the least $x$ for which $pi(x)le li(x)$.
    $endgroup$
    – DanielWainfleet
    Aug 17 at 11:47






  • 3




    $begingroup$
    The first thing I thought of is chess — 8-piece tablebases are currently on the bubble, and position counts at ply N are only up to N=13 or something — but not sure that’s “math” by your definition.
    $endgroup$
    – Jeff Y
    Aug 17 at 12:42






  • 3




    $begingroup$
    As @MarcGlisse mentions, there is a simple algorithm which simply lists all statements provable in ZFC, so with sufficient computational power you could prove anything that's provable. However, something like the Riemann hypothesis can't necessarily be resolved this way, since it might be independent from ZFC, in which case neither it nor its negation will ever be proven by the program. Indeed, the class of unsolved problems the OP is interested in is precisely the class of open problems which are known to not be independent from ZFC.
    $endgroup$
    – Jim Belk
    Aug 18 at 9:12
















49












49








49


24



$begingroup$


I was recently reading up about computational power and its uses in maths particularly to find counterexamples to conjectures. I was wondering are there any current mathematical problems which we are unable to solve due to our lack of computational power or inaccessibility to it.



What exactly am I looking for?



Problems of which we know that they can be solved with a finite (but very long) computation?



(e. g. NOT the Riemann hypothesis or twin prime conjecture)



FROM THE COMMENTS



(Maybe this will be helpful for people to understand the question in a better way if they don't already.)



There is a simple algorithm which simply lists all statements provable in
ZFC, so with sufficient computational power you could prove anything that's provable. However, something like the Riemann hypothesis can't necessarily be resolved this way, since it might be independent from ZFC, in which case neither it nor its negation will ever be proven by the program. Indeed, the class of unsolved problems I AM interested in is precisely the class of open problems which are known to not be independent from ZFC.



I am looking for specific examples.










share|cite|improve this question











$endgroup$




I was recently reading up about computational power and its uses in maths particularly to find counterexamples to conjectures. I was wondering are there any current mathematical problems which we are unable to solve due to our lack of computational power or inaccessibility to it.



What exactly am I looking for?



Problems of which we know that they can be solved with a finite (but very long) computation?



(e. g. NOT the Riemann hypothesis or twin prime conjecture)



FROM THE COMMENTS



(Maybe this will be helpful for people to understand the question in a better way if they don't already.)



There is a simple algorithm which simply lists all statements provable in
ZFC, so with sufficient computational power you could prove anything that's provable. However, something like the Riemann hypothesis can't necessarily be resolved this way, since it might be independent from ZFC, in which case neither it nor its negation will ever be proven by the program. Indeed, the class of unsolved problems I AM interested in is precisely the class of open problems which are known to not be independent from ZFC.



I am looking for specific examples.







soft-question computer-science computational-mathematics big-list computer-assisted-proofs






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 2 days ago


























community wiki





10 revs, 4 users 95%
StackUpPhysics












  • 2




    $begingroup$
    What exactly are you looking for? Problems of which we know that they can be solved with a finite (but very long) computation? (e. g. not the Riemann hypothesis or twin prime conjecture)
    $endgroup$
    – 0x539
    Aug 16 at 20:49






  • 6




    $begingroup$
    Near duplicate on MO mathoverflow.net/q/112097/30186
    $endgroup$
    – Wojowu
    Aug 17 at 9:39






  • 4




    $begingroup$
    Perhaps Skewes' number, the least $x$ for which $pi(x)le li(x)$.
    $endgroup$
    – DanielWainfleet
    Aug 17 at 11:47






  • 3




    $begingroup$
    The first thing I thought of is chess — 8-piece tablebases are currently on the bubble, and position counts at ply N are only up to N=13 or something — but not sure that’s “math” by your definition.
    $endgroup$
    – Jeff Y
    Aug 17 at 12:42






  • 3




    $begingroup$
    As @MarcGlisse mentions, there is a simple algorithm which simply lists all statements provable in ZFC, so with sufficient computational power you could prove anything that's provable. However, something like the Riemann hypothesis can't necessarily be resolved this way, since it might be independent from ZFC, in which case neither it nor its negation will ever be proven by the program. Indeed, the class of unsolved problems the OP is interested in is precisely the class of open problems which are known to not be independent from ZFC.
    $endgroup$
    – Jim Belk
    Aug 18 at 9:12
















  • 2




    $begingroup$
    What exactly are you looking for? Problems of which we know that they can be solved with a finite (but very long) computation? (e. g. not the Riemann hypothesis or twin prime conjecture)
    $endgroup$
    – 0x539
    Aug 16 at 20:49






  • 6




    $begingroup$
    Near duplicate on MO mathoverflow.net/q/112097/30186
    $endgroup$
    – Wojowu
    Aug 17 at 9:39






  • 4




    $begingroup$
    Perhaps Skewes' number, the least $x$ for which $pi(x)le li(x)$.
    $endgroup$
    – DanielWainfleet
    Aug 17 at 11:47






  • 3




    $begingroup$
    The first thing I thought of is chess — 8-piece tablebases are currently on the bubble, and position counts at ply N are only up to N=13 or something — but not sure that’s “math” by your definition.
    $endgroup$
    – Jeff Y
    Aug 17 at 12:42






  • 3




    $begingroup$
    As @MarcGlisse mentions, there is a simple algorithm which simply lists all statements provable in ZFC, so with sufficient computational power you could prove anything that's provable. However, something like the Riemann hypothesis can't necessarily be resolved this way, since it might be independent from ZFC, in which case neither it nor its negation will ever be proven by the program. Indeed, the class of unsolved problems the OP is interested in is precisely the class of open problems which are known to not be independent from ZFC.
    $endgroup$
    – Jim Belk
    Aug 18 at 9:12










2




2




$begingroup$
What exactly are you looking for? Problems of which we know that they can be solved with a finite (but very long) computation? (e. g. not the Riemann hypothesis or twin prime conjecture)
$endgroup$
– 0x539
Aug 16 at 20:49




$begingroup$
What exactly are you looking for? Problems of which we know that they can be solved with a finite (but very long) computation? (e. g. not the Riemann hypothesis or twin prime conjecture)
$endgroup$
– 0x539
Aug 16 at 20:49




6




6




$begingroup$
Near duplicate on MO mathoverflow.net/q/112097/30186
$endgroup$
– Wojowu
Aug 17 at 9:39




$begingroup$
Near duplicate on MO mathoverflow.net/q/112097/30186
$endgroup$
– Wojowu
Aug 17 at 9:39




4




4




$begingroup$
Perhaps Skewes' number, the least $x$ for which $pi(x)le li(x)$.
$endgroup$
– DanielWainfleet
Aug 17 at 11:47




$begingroup$
Perhaps Skewes' number, the least $x$ for which $pi(x)le li(x)$.
$endgroup$
– DanielWainfleet
Aug 17 at 11:47




3




3




$begingroup$
The first thing I thought of is chess — 8-piece tablebases are currently on the bubble, and position counts at ply N are only up to N=13 or something — but not sure that’s “math” by your definition.
$endgroup$
– Jeff Y
Aug 17 at 12:42




$begingroup$
The first thing I thought of is chess — 8-piece tablebases are currently on the bubble, and position counts at ply N are only up to N=13 or something — but not sure that’s “math” by your definition.
$endgroup$
– Jeff Y
Aug 17 at 12:42




3




3




$begingroup$
As @MarcGlisse mentions, there is a simple algorithm which simply lists all statements provable in ZFC, so with sufficient computational power you could prove anything that's provable. However, something like the Riemann hypothesis can't necessarily be resolved this way, since it might be independent from ZFC, in which case neither it nor its negation will ever be proven by the program. Indeed, the class of unsolved problems the OP is interested in is precisely the class of open problems which are known to not be independent from ZFC.
$endgroup$
– Jim Belk
Aug 18 at 9:12






$begingroup$
As @MarcGlisse mentions, there is a simple algorithm which simply lists all statements provable in ZFC, so with sufficient computational power you could prove anything that's provable. However, something like the Riemann hypothesis can't necessarily be resolved this way, since it might be independent from ZFC, in which case neither it nor its negation will ever be proven by the program. Indeed, the class of unsolved problems the OP is interested in is precisely the class of open problems which are known to not be independent from ZFC.
$endgroup$
– Jim Belk
Aug 18 at 9:12












16 Answers
16






active

oldest

votes


















65











$begingroup$

Goldbach's weak conjecture isn't a conjecture anymore, but before it was proved (in 2013), it had already been proved that it was true for every $n>e^{e^{16,038}}$. It was not computationally possible to test it for all numbers $nleqslant e^{e^{16,038}}$ though.






share|cite|improve this answer











$endgroup$











  • 34




    $begingroup$
    It's always pretty strange to see the "random" bounds such as this one in number theory
    $endgroup$
    – Yuriy S
    Aug 17 at 18:33






  • 1




    $begingroup$
    This is exactly the example that I had in mind when reading the question.
    $endgroup$
    – Sebastian Bechtel
    Aug 18 at 12:09



















46











$begingroup$

Some notorious problems of this kind are in discrete mathematics but involve a search space that is many magnitudes beyond what is feasible. For example, the values of certain Ramsey numbers
or the existence of a Moore graph of degree 57.






share|cite|improve this answer











$endgroup$











  • 26




    $begingroup$
    Ramsey numbers are the canonical “unfeasible computation”. As Erdős said, paraphrased by Joel H. Spencer: “Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.” On the other hand [cont’d],
    $endgroup$
    – Peter LeFanu Lumsdaine
    Aug 17 at 10:08






  • 2




    $begingroup$
    [cont’d] …values of Ramsey numbers may not quite be what the OP is after, since they’re not typically considered as “counterexamples to a conjecture” (although of course they can be seen as such, in contrived ways).
    $endgroup$
    – Peter LeFanu Lumsdaine
    Aug 17 at 10:09






  • 1




    $begingroup$
    @PeterLeFanuLumsdaine: That is shockingly delightful!
    $endgroup$
    – Daniel R. Collins
    Aug 18 at 4:24



















24











$begingroup$

If you are including games as part of “math”, chess provides some nice unsolved problems due to computational limits. The game of chess itself cannot even be weakly solved (https://en.m.wikipedia.org/wiki/Solved_game#Overview). But strong solutions are known for a subset of chess positions, those with seven or fewer (total) pieces on the board. These are called (endgame) tablebases: https://en.m.wikipedia.org/wiki/Endgame_tablebase#Background. Any position with eight or more pieces is currently at or beyond present computational resources (chess games start with 32 pieces).



Another source of difficult computation around chess is counting total positions (of certain types) after a certain number of moves. Such as the number of chess games ending in checkmate in exactly N plies (moves by one side), which is presently only known for N <= 13: https://oeis.org/A079485. Or just the total number of possible chess games consisting of N plies, which is presently only known for N <= 14: https://oeis.org/A048987.






share|cite|improve this answer











$endgroup$











  • 3




    $begingroup$
    Completely unimportant, but the number of games is known up to 15 ply: wismuth.com/chess/statistics-games.html
    $endgroup$
    – A. Rex
    Aug 18 at 15:55






  • 2




    $begingroup$
    What is your source for "the game of chess itself cannot even be weakly solved"? The article you linked itself calls this "speculation", which it might well be despite the sprawling game tree.
    $endgroup$
    – kviiri
    2 days ago










  • $begingroup$
    @kviiri Probably it means "cannot currently be weakly solved", i.e. no one has done it yet or currently has a good plan to do it.
    $endgroup$
    – Will Sawin
    yesterday



















24











$begingroup$

Historically, a very important, computationally intensive problem arising from physics was lattice QCD (LQCD). LQCD is a theoretical framework for computing basic quantities like the mass of the proton, and it was introduced by Ken Wilson back in the 70's. However, after some initial successes, this approach stagnated due to a lack of computer power. The basic problem is that our universe has an obnoxiously large number of dimensions (four, in case you were wondering), and doing integrals in four dimensions takes an insane amount of memory. I heard a story that Ken Wilson gave a talk at a conference on LQCD where he declared that "Lattice QCD is dead" as long as a certain 4D integral could not be computed, as was the case at the time he said this.



Several years (or decades) later, computer technology matured to the point that said integral could be computed, and then LQCD theory picked right back up where it left off. Today it is again a flourishing discipline. However, other problems arising from LQCD continue to push supercomputer technology. Apparently LQCD is used as a benchmark for supercomputers nowadays.






share|cite|improve this answer











$endgroup$











  • 3




    $begingroup$
    A recent result: arxiv.org/abs/1406.4088
    $endgroup$
    – Count Iblis
    Aug 18 at 2:16










  • $begingroup$
    Here's a reference to Ken Wilson's comments (see bottom of page 10): arxiv.org/pdf/1407.1855.pdf
    $endgroup$
    – Yly
    2 days ago



















21











$begingroup$

Packing problems come to mind, i.e. how to achieve the densest packing of some kind of geometric objects, such as spheres or dodecahedrons. The interesting thing is that this is not a discrete problem, as there are uncountably many irregular, non-periodic packings that need to be checked. Still, the original proof of the sphere packing problem managed to turn this into a finite number of linear programming problems which then could be solved on a computer.



In theory you can use the same approach for objects other than spheres or in higher dimensions (and indeed people do), but in practice you reach a point quite soon, where there is simply not enough computing power to solve the resulting problems.






share|cite|improve this answer











$endgroup$























    14











    $begingroup$

    Is $e^{e^{e^{79}}}$ an integer? See this question for some background. Many other problems of this type are also technically unsolved, although the answer is almost definitely "no". This can be verified by a finite computation, but the sheer size of the numbers involved means that this is not feasible at the moment.



    Note: as pointed out by @ruakh, if $e^{e^{e^{79}}}$ were, in fact, an integer, then a naïve finite computation would not be able to resolve the question. [Of course, this seems highly unlikely, but it is not known to be false absent proof.]






    share|cite|improve this answer











    $endgroup$















    • $begingroup$
      Nice to know about this. Thanks for pointing it out
      $endgroup$
      – StackUpPhysics
      Aug 18 at 13:29










    • $begingroup$
      This answer is thought-provoking (+1), but as far as I can tell it's not actually correct: if the answer is "no" then that could be verified by a finite computation that approximated it closely enough to rule out the neighboring integers; but if the answer is "yes" then there's no obvious computational way to prove it. All we could show is that it's within ε of an integer for ridiculously small values of ε. (In fact, this very issue was the motivation for the question you link to: see https://math.stackexchange.com/a/13052/19345.)
      $endgroup$
      – ruakh
      yesterday












    • $begingroup$
      @ruakh Wow, I hadn't thought of that. You're right, I will edit the answer to reflect that later.
      $endgroup$
      – YiFan
      yesterday



















    11











    $begingroup$

    It is strongly believed that the second Hardy-Littlewood conjecture is false, because it contradicts the first Hardy-Littlewood conjecture, which has the backing of not only the probabilistic heuristic but also a lot of recent work. The second link even states that if the first conjecture (also called the prime $k$-tuples conjecture) holds, then there are in fact infinitely many positive integers $x$ such that $π(x+3159)-π(x) = 447 > 446 = π(3159)$. This is obviously something that can be verified with sufficient computational power (simply test every positive integer $x$ until you find one that satisfies the desired inequality), but clearly it has not been done yet otherwise we would have heard news of it!






    share|cite|improve this answer











    $endgroup$















    • $begingroup$
      Interesting to get to know about this. Haven't heard about this conjecture before
      $endgroup$
      – StackUpPhysics
      Aug 18 at 13:28










    • $begingroup$
      I don't think this answers the question. It's structurally very similar to disproving the Riemann hypothesis, which is explicitly given as an example of something the OP doesn't want.
      $endgroup$
      – Brady Gilg
      2 days ago










    • $begingroup$
      @BradyGilg: Note that I answered the question before it was significantly changed. Besides, this is quite different from disproving RH because people believe RH is true (so it shouldn't be disprovable) whereas people believe that the conjecture stated in my post is true and hence provable by a finite computation.
      $endgroup$
      – user21820
      2 days ago



















    8











    $begingroup$

    Optimal sorting networks
    for $n>10$.




    For small, fixed numbers of inputs n, optimal sorting networks can be
    constructed, with either minimal depth (for maximally parallel
    execution) or minimal size (number of comparators)... The following
    table summarizes the known optimality results:




    $$ begin{array}{l|ccccccccccccccccc|} hline n & 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17 \ hline text{Depth} & 0& 1& 3& 3& 5& 5& 6& 6& 7& 7& 8& 8& 9& 9& 9& 9& 10 \ hline text{Size, upper bound} & 0& 1& 3& 5& 9& 12& 16& 19& 25& 29& 35& 39& 45& 51& 56& 60& 71 \ hline text{Size, lower bound (if different)} & & & & & & & & & & & 33& 37& 41& 45& 49& 53& 58 \ hline end{array} $$






    share|cite|improve this answer











    $endgroup$











    • 1




      $begingroup$
      can you elaborate in the answer?
      $endgroup$
      – Kai
      Aug 18 at 17:15










    • $begingroup$
      @ Kai : updated
      $endgroup$
      – g.kov
      Aug 18 at 18:50



















    7











    $begingroup$

    Euler's conjecture that it takes $n$ $n$th powers to sum to an $n$ power is true for $n=3$ but proven false for $n=4,5$, for example,



    $$27^5+ 84^5+110^5+ 133^5= 144^5qquadtext{(found in 1966)}$$
    $$95800^4 + 217519^4 + 414560^4 = 422481^4qquadtext{(found in 1988)}$$



    but nobody knows if it is false for any or all $ngeq6$. There are heuristics that suggest,



    $$x_1^6+x_2^6+dots+x_5^6 = z^6$$



    has positive solutions as well and a fast enough computer might find it. For the moment, such computational power is not available to individuals.






    share|cite|improve this answer











    $endgroup$











    • 4




      $begingroup$
      Interesting problem, but it does not seem to match: "Problems of which we know that they can be solved with a finite (but very long) computation? " (my emphasis).
      $endgroup$
      – quid
      Aug 18 at 11:32



















    6











    $begingroup$

    The order of every finite projective plane is a prime power. If this is false, a counterexample can be constructed by exhaustive search of all non-prime powers in increasing order. This has been done by hand for $n=6$ and by computer for $n=10$, but as far as I know, $n=12$ is still out of reach, or at least, it hasn't been done.






    share|cite|improve this answer











    $endgroup$











    • 4




      $begingroup$
      My understanding of the question suggests that this isn't an example unless there's some upper bound at which point we can stop. My interpretation of the question is the problems need to be computationally decidable, not semidecidable. Otherwise, we could say of any (formal) theorem that "if it's 'true', then we can enumerate proofs until we find its proof". Of course, you could say the $n=12$ case is decidable, but it still seems to miss the spirit of the question unless there's something special about this case. I could just as well ask if a theorem has a proof of size at most $N$.
      $endgroup$
      – Derek Elkins
      Aug 18 at 1:57










    • $begingroup$
      An alternative conjecture used to be that a finite projective plane exists for every order not ruled out by the Bruck-Ryser theorem. Orders 6 and 14 are so ruled out, but orders 10 and 12 are not. This conjecture is, of course, dead now that a plane of order 10 has been ruled out by computational means. But I think many people still would like to know whether a plane of order 12 exists.
      $endgroup$
      – Will Orrick
      Aug 18 at 12:23












    • $begingroup$
      Is it believed that there is a finite projective plane with order not a prime power?
      $endgroup$
      – user21820
      2 days ago










    • $begingroup$
      @user21820 I'm not a worker in the field, so I can't really say. In 1995, Gary Mullen suggested it as a candidate for "the next Fermat problem" Unfortunately, Springer doesn't make the whole article available publicly. The MOLS problem he discusses is equivalent to the finite projective plane problem. See pi.math.cornell.edu/~web4520/CG9-0.pdf
      $endgroup$
      – saulspatz
      2 days ago












    • $begingroup$
      Thanks! Upon accessing the full paper, it says that: Kirkman established the existence of projective planes of prime power order around 1850, and Bose showed the equivalence of having $n - 1$ MOLS of order $n$ and having a projective plane of order $n$. Bruck and Ryser proved that if $n$ is $1$ or $2$ mod $4$ and the square-free part of $n$ has at least one prime factor of the form $4k + 3$, then there cannot be $n-1$ MOLS of order $n$. This result was proven using numerous number-theoretic techniques, including Lagrange's 4-square theorem.
      $endgroup$
      – user21820
      2 days ago



















    4











    $begingroup$

    Littlewood proved in 1914 that there exists a number $ninmathbb{N}$ (called Skewes' number) such that:



    $$
    pi(n) > operatorname{li}(n),
    $$



    where $pi(n)$ is the amount of primes below $n$ and $operatorname{li}(n)$ denotes the logarithmic integral $displaystyle int_0^n frac{dt}{ln t}$.



    It is conjectured that $n$ is a huge number, recent analysis suggests $napprox e^{727.951}$. Since then, researchers have worked to find lower and upper bounds for $n$. Currently it is held that:



    $$
    10^{19}<n<e^{727.951}.
    $$



    No such number has been found yet.






    share|cite|improve this answer











    $endgroup$















    • $begingroup$
      Is it actually believed that Skewes' number is $approx e^{727}$? I thought I'd previously read that a crossing point is there but not necessarily the least crossing point (Skewes'), which as you point out could be as low as $10^{19}$
      $endgroup$
      – Jam
      2 days ago





















    3











    $begingroup$

    There was the question: Are there m consecutive positive integers from k to k+m-1 which contain more primes than the m integers from 2 to m+1?



    The problem itself is unsolved, but there is a hypothesis with the twin-prime hypothesis as the simplest special case:



    Given n ≥ 2, and n integers $0 = k_1 < k_2 < ... < k_n$, and for every prime p ≤ n the set of remainders $k_i mod p$ has fewer than p elements, then there are infinitely many integers p such that $p + k_i$ is prime for every 1 ≤ i ≤ n.



    If there are n primes from 2 to 2+m-1, and we find $k_1$ to $k_{n+1}$ with $k_{n+1} ≤ m-1$, then the hypothesis is that there are infinitely many sequences of m consecutive integers containing n+1 primes.



    Finding such a sequence was quite hard but was done. I think there are sequences known that point to 5 more primes in m consecutive integers than in 2 to m-1, but beyond that it's limited by processing power (or by willingness to use that processing power).






    share|cite|improve this answer











    $endgroup$











    • 1




      $begingroup$
      The 1st paragraph is called the Hardy-Littlewood 2nd conjecture, the 3rd paragraph id called the Hardy-Littlewood 1st conjecture, see the answer from user21820.
      $endgroup$
      – Gerry Myerson
      2 days ago



















    3











    $begingroup$

    The number of distinct magic squares, for deceptively small sizes



    A magic square of order $n$ is a square grid of $n times n$ boxes where each box contains one distinct integer from the interval $[1 .. n^2]$, so that the sums of the numbers on each row, on each column and on each of the two diagonals are equal to each other. They have been studied for millenia by mathematicians in China, India and Persia, and continue to be of interest to both hobbyist and professional mathematicians.



    The smallest magic squares, excluding the trivial case where $n = 1$, are of order $3$. This is one of them:



    begin{array}{|c|c|c|}
    hline
    8 & 3 & 4 \ hline
    1 & 5 & 9 \ hline
    6 & 7 & 2 \ hline
    end{array}



    In a sense, this is the only solution to the problem of this size: the other 7 magic squares of order 3 are mirrored and/or rotated versions of this grid.



    We know the number of magic squares of orders 3, 4 and 5. The number of magic squares of order 6 is not known, but is believed to be in the order of $10^{19}$. The number of magic squares is not known for any order greater than 6 either. It should be noted that constructing magic squares of odd and doubly-even (divisible by four) orders is generally regarded as a simpler feat than constructing magic squares of singly-even orders like 6, although this may not guarantee the ease of enumerating all magic squares of such order over enumerating those of orders of smaller singly even numbers.



    This problem is trivially solvable if the computational power constraint wouldn't stop us: we could just enumerate all $36!$ possible ways to fit the numbers in the grid, and check each for magic number property. In practice, we can apply a fair bit of pruning to explore only a small fraction of this space. We know the sum that should appear on each row/column/diagonal and we know that only an eighth of the configurations need to be checked to account for their mirrored and/or rotated copies; these and further insights or heuristics may be enough to make the problem computationally tractable for a well-supplied research effort in the coming years.



    However, this is in a sense cop-out; even if we solve the number of magic squares of order 6, we'll still be left wondering what the number of magic squares of order 7 and greater might be --- that is, unless someone figures out a more efficient way to compute it than raw enumeration.






    share|cite|improve this answer











    $endgroup$















    • $begingroup$
      Reading this Parker's Square comes to my mind if you know what I mean
      $endgroup$
      – StackUpPhysics
      2 days ago










    • $begingroup$
      The reference if you didn't get it- bradyharanblog.com/the-parker-square
      $endgroup$
      – StackUpPhysics
      2 days ago



















    0











    $begingroup$

    I believe a problem connected with Graham's number is one of the things you are looking for. It is an upper bound to problem in Ramsey theory, that looks for a number $N$ satisfying certain criteria. I do not know much about that, but you can read more here https://en.wikipedia.org/wiki/Graham%27s_number .



    But from my understanding, there are bounds on the number $N$, however the range of possible values derived from those bounds is still enormously large, way beyond computational possibilities of today (and probably ever). But with arbitrarily large, yet still finite computational power, the problem could be solved.






    share|cite|improve this answer











    $endgroup$























      0











      $begingroup$

      What are the odds in Klondike Solitare? An attempt was made based on perfect knowledge yielding 79%, but the player doesn't have perfect knowledge. There's a bunch of Monte-Carlo results on that site; but a direct attack is far beyond reach, and it's not even known if the strategy they're using is actually optimal.



      "One of the embarrassments of applied mathematics that we cannot determine the odds of winning the common game of solitaire."






      share|cite|improve this answer











      $endgroup$























        -2











        $begingroup$

        Prime gaps - https://en.wikipedia.org/wiki/Prime_gap - of maximum known merit are found by increasing CPU (and GPU) computational power on the gapcoin network. See: https://gapcoin.club




        ... So the difficulty will simply be the length of the prime gap?



        Not exactly. The average length of a prime gap with the starting prime
        p, is log(p), which means that the average prime gap size increases
        with lager primes. Then, instead of the pure length, we use the merit
        of the prime gap, which is the ratio of the gap's size to the average
        gap size.



        Let p be the prime starting a prime gap, then m = gapsize/log(p) will
        be the merit of this prime gap.



        Also a pseudo random number is calculated from p to provide finer
        difficulty adjustment.



        Let rand(p) be a pseudo random function with 0 less than rand(p) less
        than 1. Then, for a prime gap starting at prime p with size s, the
        difficulty will be s/log(p) + 2/log(p) * rand(p), where 2/log(p) is
        the average distance between a gap of size s and s + 2 (the next
        greater gap) in the proximity of p.



        When it actually comes to mining, there are two additional fields
        added to the Blockheader, named “shift” and “adder”. We will calculate
        the prime p as sha256(Blockheader) * 2^shift + adder. As an additional
        criterion the adder has to be smaller than 2^shift to avoid that the
        PoW could be reused. ...




        Source: gapcoin.org



        ...



        https://web.stanford.edu/~tonyfeng/bounded_gaps.pdf




        ... (Twin prime conjecture) ...



        ... This is a just a special case of a far-reaching conjecture
        of Hardy and Lit- tlewood describing the frequency of prime
        gaps of any sizes. The Hardy- Littlewood conjecture predicts not
        only how often twin primes occur, but also how often any finite
        tuple
        of the form ( n
        + h 1 , n
        + h 2 , . . . , n
        + h k ) consists en- tirely of prime numbers. But even though analytic number theorists have be- lieved for many years that they know the
        answers to these questions, progress towards proving the existence of
        small gaps between primes has been slow. As recently as 2005 , the
        problem of establishing infinitely many bounded gaps be- tween primes
        was considered by many mathematicians to be “hopeless” ...




        ...



        Further,



        List of unsolved problems in mathematics:
        https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics






        share|cite|improve this answer











        $endgroup$















        • $begingroup$
          The OP wants a problem that is known to be solvable with a finite algorithm, which afaik is not known to exist for finding either the primegap of maximum merit nor the twin prime conjecture.
          $endgroup$
          – Jam
          2 days ago














        Your Answer








        StackExchange.ready(function() {
        var channelOptions = {
        tags: "".split(" "),
        id: "69"
        };
        initTagRenderer("".split(" "), "".split(" "), channelOptions);

        StackExchange.using("externalEditor", function() {
        // Have to fire editor after snippets, if snippets enabled
        if (StackExchange.settings.snippets.snippetsEnabled) {
        StackExchange.using("snippets", function() {
        createEditor();
        });
        }
        else {
        createEditor();
        }
        });

        function createEditor() {
        StackExchange.prepareEditor({
        heartbeatType: 'answer',
        autoActivateHeartbeat: false,
        convertImagesToLinks: true,
        noModals: true,
        showLowRepImageUploadWarning: true,
        reputationToPostImages: 10,
        bindNavPrevention: true,
        postfix: "",
        imageUploader: {
        brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
        contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
        allowUrls: true
        },
        noCode: true, onDemand: true,
        discardSelector: ".discard-answer"
        ,immediatelyShowMarkdownHelp:true
        });


        }
        });














        draft saved

        draft discarded


















        StackExchange.ready(
        function () {
        StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3325462%2funsolved-problems-not-independent-of-zfc-due-to-lack-of-computational-power%23new-answer', 'question_page');
        }
        );

        Post as a guest















        Required, but never shown

























        16 Answers
        16






        active

        oldest

        votes








        16 Answers
        16






        active

        oldest

        votes









        active

        oldest

        votes






        active

        oldest

        votes









        65











        $begingroup$

        Goldbach's weak conjecture isn't a conjecture anymore, but before it was proved (in 2013), it had already been proved that it was true for every $n>e^{e^{16,038}}$. It was not computationally possible to test it for all numbers $nleqslant e^{e^{16,038}}$ though.






        share|cite|improve this answer











        $endgroup$











        • 34




          $begingroup$
          It's always pretty strange to see the "random" bounds such as this one in number theory
          $endgroup$
          – Yuriy S
          Aug 17 at 18:33






        • 1




          $begingroup$
          This is exactly the example that I had in mind when reading the question.
          $endgroup$
          – Sebastian Bechtel
          Aug 18 at 12:09
















        65











        $begingroup$

        Goldbach's weak conjecture isn't a conjecture anymore, but before it was proved (in 2013), it had already been proved that it was true for every $n>e^{e^{16,038}}$. It was not computationally possible to test it for all numbers $nleqslant e^{e^{16,038}}$ though.






        share|cite|improve this answer











        $endgroup$











        • 34




          $begingroup$
          It's always pretty strange to see the "random" bounds such as this one in number theory
          $endgroup$
          – Yuriy S
          Aug 17 at 18:33






        • 1




          $begingroup$
          This is exactly the example that I had in mind when reading the question.
          $endgroup$
          – Sebastian Bechtel
          Aug 18 at 12:09














        65












        65








        65





        $begingroup$

        Goldbach's weak conjecture isn't a conjecture anymore, but before it was proved (in 2013), it had already been proved that it was true for every $n>e^{e^{16,038}}$. It was not computationally possible to test it for all numbers $nleqslant e^{e^{16,038}}$ though.






        share|cite|improve this answer











        $endgroup$



        Goldbach's weak conjecture isn't a conjecture anymore, but before it was proved (in 2013), it had already been proved that it was true for every $n>e^{e^{16,038}}$. It was not computationally possible to test it for all numbers $nleqslant e^{e^{16,038}}$ though.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Aug 16 at 21:29


























        community wiki





        José Carlos Santos












        • 34




          $begingroup$
          It's always pretty strange to see the "random" bounds such as this one in number theory
          $endgroup$
          – Yuriy S
          Aug 17 at 18:33






        • 1




          $begingroup$
          This is exactly the example that I had in mind when reading the question.
          $endgroup$
          – Sebastian Bechtel
          Aug 18 at 12:09














        • 34




          $begingroup$
          It's always pretty strange to see the "random" bounds such as this one in number theory
          $endgroup$
          – Yuriy S
          Aug 17 at 18:33






        • 1




          $begingroup$
          This is exactly the example that I had in mind when reading the question.
          $endgroup$
          – Sebastian Bechtel
          Aug 18 at 12:09








        34




        34




        $begingroup$
        It's always pretty strange to see the "random" bounds such as this one in number theory
        $endgroup$
        – Yuriy S
        Aug 17 at 18:33




        $begingroup$
        It's always pretty strange to see the "random" bounds such as this one in number theory
        $endgroup$
        – Yuriy S
        Aug 17 at 18:33




        1




        1




        $begingroup$
        This is exactly the example that I had in mind when reading the question.
        $endgroup$
        – Sebastian Bechtel
        Aug 18 at 12:09




        $begingroup$
        This is exactly the example that I had in mind when reading the question.
        $endgroup$
        – Sebastian Bechtel
        Aug 18 at 12:09













        46











        $begingroup$

        Some notorious problems of this kind are in discrete mathematics but involve a search space that is many magnitudes beyond what is feasible. For example, the values of certain Ramsey numbers
        or the existence of a Moore graph of degree 57.






        share|cite|improve this answer











        $endgroup$











        • 26




          $begingroup$
          Ramsey numbers are the canonical “unfeasible computation”. As Erdős said, paraphrased by Joel H. Spencer: “Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.” On the other hand [cont’d],
          $endgroup$
          – Peter LeFanu Lumsdaine
          Aug 17 at 10:08






        • 2




          $begingroup$
          [cont’d] …values of Ramsey numbers may not quite be what the OP is after, since they’re not typically considered as “counterexamples to a conjecture” (although of course they can be seen as such, in contrived ways).
          $endgroup$
          – Peter LeFanu Lumsdaine
          Aug 17 at 10:09






        • 1




          $begingroup$
          @PeterLeFanuLumsdaine: That is shockingly delightful!
          $endgroup$
          – Daniel R. Collins
          Aug 18 at 4:24
















        46











        $begingroup$

        Some notorious problems of this kind are in discrete mathematics but involve a search space that is many magnitudes beyond what is feasible. For example, the values of certain Ramsey numbers
        or the existence of a Moore graph of degree 57.






        share|cite|improve this answer











        $endgroup$











        • 26




          $begingroup$
          Ramsey numbers are the canonical “unfeasible computation”. As Erdős said, paraphrased by Joel H. Spencer: “Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.” On the other hand [cont’d],
          $endgroup$
          – Peter LeFanu Lumsdaine
          Aug 17 at 10:08






        • 2




          $begingroup$
          [cont’d] …values of Ramsey numbers may not quite be what the OP is after, since they’re not typically considered as “counterexamples to a conjecture” (although of course they can be seen as such, in contrived ways).
          $endgroup$
          – Peter LeFanu Lumsdaine
          Aug 17 at 10:09






        • 1




          $begingroup$
          @PeterLeFanuLumsdaine: That is shockingly delightful!
          $endgroup$
          – Daniel R. Collins
          Aug 18 at 4:24














        46












        46








        46





        $begingroup$

        Some notorious problems of this kind are in discrete mathematics but involve a search space that is many magnitudes beyond what is feasible. For example, the values of certain Ramsey numbers
        or the existence of a Moore graph of degree 57.






        share|cite|improve this answer











        $endgroup$



        Some notorious problems of this kind are in discrete mathematics but involve a search space that is many magnitudes beyond what is feasible. For example, the values of certain Ramsey numbers
        or the existence of a Moore graph of degree 57.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Aug 18 at 22:57


























        community wiki





        2 revs, 2 users 57%
        ahulpke












        • 26




          $begingroup$
          Ramsey numbers are the canonical “unfeasible computation”. As Erdős said, paraphrased by Joel H. Spencer: “Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.” On the other hand [cont’d],
          $endgroup$
          – Peter LeFanu Lumsdaine
          Aug 17 at 10:08






        • 2




          $begingroup$
          [cont’d] …values of Ramsey numbers may not quite be what the OP is after, since they’re not typically considered as “counterexamples to a conjecture” (although of course they can be seen as such, in contrived ways).
          $endgroup$
          – Peter LeFanu Lumsdaine
          Aug 17 at 10:09






        • 1




          $begingroup$
          @PeterLeFanuLumsdaine: That is shockingly delightful!
          $endgroup$
          – Daniel R. Collins
          Aug 18 at 4:24














        • 26




          $begingroup$
          Ramsey numbers are the canonical “unfeasible computation”. As Erdős said, paraphrased by Joel H. Spencer: “Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.” On the other hand [cont’d],
          $endgroup$
          – Peter LeFanu Lumsdaine
          Aug 17 at 10:08






        • 2




          $begingroup$
          [cont’d] …values of Ramsey numbers may not quite be what the OP is after, since they’re not typically considered as “counterexamples to a conjecture” (although of course they can be seen as such, in contrived ways).
          $endgroup$
          – Peter LeFanu Lumsdaine
          Aug 17 at 10:09






        • 1




          $begingroup$
          @PeterLeFanuLumsdaine: That is shockingly delightful!
          $endgroup$
          – Daniel R. Collins
          Aug 18 at 4:24








        26




        26




        $begingroup$
        Ramsey numbers are the canonical “unfeasible computation”. As Erdős said, paraphrased by Joel H. Spencer: “Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.” On the other hand [cont’d],
        $endgroup$
        – Peter LeFanu Lumsdaine
        Aug 17 at 10:08




        $begingroup$
        Ramsey numbers are the canonical “unfeasible computation”. As Erdős said, paraphrased by Joel H. Spencer: “Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.” On the other hand [cont’d],
        $endgroup$
        – Peter LeFanu Lumsdaine
        Aug 17 at 10:08




        2




        2




        $begingroup$
        [cont’d] …values of Ramsey numbers may not quite be what the OP is after, since they’re not typically considered as “counterexamples to a conjecture” (although of course they can be seen as such, in contrived ways).
        $endgroup$
        – Peter LeFanu Lumsdaine
        Aug 17 at 10:09




        $begingroup$
        [cont’d] …values of Ramsey numbers may not quite be what the OP is after, since they’re not typically considered as “counterexamples to a conjecture” (although of course they can be seen as such, in contrived ways).
        $endgroup$
        – Peter LeFanu Lumsdaine
        Aug 17 at 10:09




        1




        1




        $begingroup$
        @PeterLeFanuLumsdaine: That is shockingly delightful!
        $endgroup$
        – Daniel R. Collins
        Aug 18 at 4:24




        $begingroup$
        @PeterLeFanuLumsdaine: That is shockingly delightful!
        $endgroup$
        – Daniel R. Collins
        Aug 18 at 4:24











        24











        $begingroup$

        If you are including games as part of “math”, chess provides some nice unsolved problems due to computational limits. The game of chess itself cannot even be weakly solved (https://en.m.wikipedia.org/wiki/Solved_game#Overview). But strong solutions are known for a subset of chess positions, those with seven or fewer (total) pieces on the board. These are called (endgame) tablebases: https://en.m.wikipedia.org/wiki/Endgame_tablebase#Background. Any position with eight or more pieces is currently at or beyond present computational resources (chess games start with 32 pieces).



        Another source of difficult computation around chess is counting total positions (of certain types) after a certain number of moves. Such as the number of chess games ending in checkmate in exactly N plies (moves by one side), which is presently only known for N <= 13: https://oeis.org/A079485. Or just the total number of possible chess games consisting of N plies, which is presently only known for N <= 14: https://oeis.org/A048987.






        share|cite|improve this answer











        $endgroup$











        • 3




          $begingroup$
          Completely unimportant, but the number of games is known up to 15 ply: wismuth.com/chess/statistics-games.html
          $endgroup$
          – A. Rex
          Aug 18 at 15:55






        • 2




          $begingroup$
          What is your source for "the game of chess itself cannot even be weakly solved"? The article you linked itself calls this "speculation", which it might well be despite the sprawling game tree.
          $endgroup$
          – kviiri
          2 days ago










        • $begingroup$
          @kviiri Probably it means "cannot currently be weakly solved", i.e. no one has done it yet or currently has a good plan to do it.
          $endgroup$
          – Will Sawin
          yesterday
















        24











        $begingroup$

        If you are including games as part of “math”, chess provides some nice unsolved problems due to computational limits. The game of chess itself cannot even be weakly solved (https://en.m.wikipedia.org/wiki/Solved_game#Overview). But strong solutions are known for a subset of chess positions, those with seven or fewer (total) pieces on the board. These are called (endgame) tablebases: https://en.m.wikipedia.org/wiki/Endgame_tablebase#Background. Any position with eight or more pieces is currently at or beyond present computational resources (chess games start with 32 pieces).



        Another source of difficult computation around chess is counting total positions (of certain types) after a certain number of moves. Such as the number of chess games ending in checkmate in exactly N plies (moves by one side), which is presently only known for N <= 13: https://oeis.org/A079485. Or just the total number of possible chess games consisting of N plies, which is presently only known for N <= 14: https://oeis.org/A048987.






        share|cite|improve this answer











        $endgroup$











        • 3




          $begingroup$
          Completely unimportant, but the number of games is known up to 15 ply: wismuth.com/chess/statistics-games.html
          $endgroup$
          – A. Rex
          Aug 18 at 15:55






        • 2




          $begingroup$
          What is your source for "the game of chess itself cannot even be weakly solved"? The article you linked itself calls this "speculation", which it might well be despite the sprawling game tree.
          $endgroup$
          – kviiri
          2 days ago










        • $begingroup$
          @kviiri Probably it means "cannot currently be weakly solved", i.e. no one has done it yet or currently has a good plan to do it.
          $endgroup$
          – Will Sawin
          yesterday














        24












        24








        24





        $begingroup$

        If you are including games as part of “math”, chess provides some nice unsolved problems due to computational limits. The game of chess itself cannot even be weakly solved (https://en.m.wikipedia.org/wiki/Solved_game#Overview). But strong solutions are known for a subset of chess positions, those with seven or fewer (total) pieces on the board. These are called (endgame) tablebases: https://en.m.wikipedia.org/wiki/Endgame_tablebase#Background. Any position with eight or more pieces is currently at or beyond present computational resources (chess games start with 32 pieces).



        Another source of difficult computation around chess is counting total positions (of certain types) after a certain number of moves. Such as the number of chess games ending in checkmate in exactly N plies (moves by one side), which is presently only known for N <= 13: https://oeis.org/A079485. Or just the total number of possible chess games consisting of N plies, which is presently only known for N <= 14: https://oeis.org/A048987.






        share|cite|improve this answer











        $endgroup$



        If you are including games as part of “math”, chess provides some nice unsolved problems due to computational limits. The game of chess itself cannot even be weakly solved (https://en.m.wikipedia.org/wiki/Solved_game#Overview). But strong solutions are known for a subset of chess positions, those with seven or fewer (total) pieces on the board. These are called (endgame) tablebases: https://en.m.wikipedia.org/wiki/Endgame_tablebase#Background. Any position with eight or more pieces is currently at or beyond present computational resources (chess games start with 32 pieces).



        Another source of difficult computation around chess is counting total positions (of certain types) after a certain number of moves. Such as the number of chess games ending in checkmate in exactly N plies (moves by one side), which is presently only known for N <= 13: https://oeis.org/A079485. Or just the total number of possible chess games consisting of N plies, which is presently only known for N <= 14: https://oeis.org/A048987.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        answered Aug 17 at 19:51


























        community wiki





        Jeff Y












        • 3




          $begingroup$
          Completely unimportant, but the number of games is known up to 15 ply: wismuth.com/chess/statistics-games.html
          $endgroup$
          – A. Rex
          Aug 18 at 15:55






        • 2




          $begingroup$
          What is your source for "the game of chess itself cannot even be weakly solved"? The article you linked itself calls this "speculation", which it might well be despite the sprawling game tree.
          $endgroup$
          – kviiri
          2 days ago










        • $begingroup$
          @kviiri Probably it means "cannot currently be weakly solved", i.e. no one has done it yet or currently has a good plan to do it.
          $endgroup$
          – Will Sawin
          yesterday














        • 3




          $begingroup$
          Completely unimportant, but the number of games is known up to 15 ply: wismuth.com/chess/statistics-games.html
          $endgroup$
          – A. Rex
          Aug 18 at 15:55






        • 2




          $begingroup$
          What is your source for "the game of chess itself cannot even be weakly solved"? The article you linked itself calls this "speculation", which it might well be despite the sprawling game tree.
          $endgroup$
          – kviiri
          2 days ago










        • $begingroup$
          @kviiri Probably it means "cannot currently be weakly solved", i.e. no one has done it yet or currently has a good plan to do it.
          $endgroup$
          – Will Sawin
          yesterday








        3




        3




        $begingroup$
        Completely unimportant, but the number of games is known up to 15 ply: wismuth.com/chess/statistics-games.html
        $endgroup$
        – A. Rex
        Aug 18 at 15:55




        $begingroup$
        Completely unimportant, but the number of games is known up to 15 ply: wismuth.com/chess/statistics-games.html
        $endgroup$
        – A. Rex
        Aug 18 at 15:55




        2




        2




        $begingroup$
        What is your source for "the game of chess itself cannot even be weakly solved"? The article you linked itself calls this "speculation", which it might well be despite the sprawling game tree.
        $endgroup$
        – kviiri
        2 days ago




        $begingroup$
        What is your source for "the game of chess itself cannot even be weakly solved"? The article you linked itself calls this "speculation", which it might well be despite the sprawling game tree.
        $endgroup$
        – kviiri
        2 days ago












        $begingroup$
        @kviiri Probably it means "cannot currently be weakly solved", i.e. no one has done it yet or currently has a good plan to do it.
        $endgroup$
        – Will Sawin
        yesterday




        $begingroup$
        @kviiri Probably it means "cannot currently be weakly solved", i.e. no one has done it yet or currently has a good plan to do it.
        $endgroup$
        – Will Sawin
        yesterday











        24











        $begingroup$

        Historically, a very important, computationally intensive problem arising from physics was lattice QCD (LQCD). LQCD is a theoretical framework for computing basic quantities like the mass of the proton, and it was introduced by Ken Wilson back in the 70's. However, after some initial successes, this approach stagnated due to a lack of computer power. The basic problem is that our universe has an obnoxiously large number of dimensions (four, in case you were wondering), and doing integrals in four dimensions takes an insane amount of memory. I heard a story that Ken Wilson gave a talk at a conference on LQCD where he declared that "Lattice QCD is dead" as long as a certain 4D integral could not be computed, as was the case at the time he said this.



        Several years (or decades) later, computer technology matured to the point that said integral could be computed, and then LQCD theory picked right back up where it left off. Today it is again a flourishing discipline. However, other problems arising from LQCD continue to push supercomputer technology. Apparently LQCD is used as a benchmark for supercomputers nowadays.






        share|cite|improve this answer











        $endgroup$











        • 3




          $begingroup$
          A recent result: arxiv.org/abs/1406.4088
          $endgroup$
          – Count Iblis
          Aug 18 at 2:16










        • $begingroup$
          Here's a reference to Ken Wilson's comments (see bottom of page 10): arxiv.org/pdf/1407.1855.pdf
          $endgroup$
          – Yly
          2 days ago
















        24











        $begingroup$

        Historically, a very important, computationally intensive problem arising from physics was lattice QCD (LQCD). LQCD is a theoretical framework for computing basic quantities like the mass of the proton, and it was introduced by Ken Wilson back in the 70's. However, after some initial successes, this approach stagnated due to a lack of computer power. The basic problem is that our universe has an obnoxiously large number of dimensions (four, in case you were wondering), and doing integrals in four dimensions takes an insane amount of memory. I heard a story that Ken Wilson gave a talk at a conference on LQCD where he declared that "Lattice QCD is dead" as long as a certain 4D integral could not be computed, as was the case at the time he said this.



        Several years (or decades) later, computer technology matured to the point that said integral could be computed, and then LQCD theory picked right back up where it left off. Today it is again a flourishing discipline. However, other problems arising from LQCD continue to push supercomputer technology. Apparently LQCD is used as a benchmark for supercomputers nowadays.






        share|cite|improve this answer











        $endgroup$











        • 3




          $begingroup$
          A recent result: arxiv.org/abs/1406.4088
          $endgroup$
          – Count Iblis
          Aug 18 at 2:16










        • $begingroup$
          Here's a reference to Ken Wilson's comments (see bottom of page 10): arxiv.org/pdf/1407.1855.pdf
          $endgroup$
          – Yly
          2 days ago














        24












        24








        24





        $begingroup$

        Historically, a very important, computationally intensive problem arising from physics was lattice QCD (LQCD). LQCD is a theoretical framework for computing basic quantities like the mass of the proton, and it was introduced by Ken Wilson back in the 70's. However, after some initial successes, this approach stagnated due to a lack of computer power. The basic problem is that our universe has an obnoxiously large number of dimensions (four, in case you were wondering), and doing integrals in four dimensions takes an insane amount of memory. I heard a story that Ken Wilson gave a talk at a conference on LQCD where he declared that "Lattice QCD is dead" as long as a certain 4D integral could not be computed, as was the case at the time he said this.



        Several years (or decades) later, computer technology matured to the point that said integral could be computed, and then LQCD theory picked right back up where it left off. Today it is again a flourishing discipline. However, other problems arising from LQCD continue to push supercomputer technology. Apparently LQCD is used as a benchmark for supercomputers nowadays.






        share|cite|improve this answer











        $endgroup$



        Historically, a very important, computationally intensive problem arising from physics was lattice QCD (LQCD). LQCD is a theoretical framework for computing basic quantities like the mass of the proton, and it was introduced by Ken Wilson back in the 70's. However, after some initial successes, this approach stagnated due to a lack of computer power. The basic problem is that our universe has an obnoxiously large number of dimensions (four, in case you were wondering), and doing integrals in four dimensions takes an insane amount of memory. I heard a story that Ken Wilson gave a talk at a conference on LQCD where he declared that "Lattice QCD is dead" as long as a certain 4D integral could not be computed, as was the case at the time he said this.



        Several years (or decades) later, computer technology matured to the point that said integral could be computed, and then LQCD theory picked right back up where it left off. Today it is again a flourishing discipline. However, other problems arising from LQCD continue to push supercomputer technology. Apparently LQCD is used as a benchmark for supercomputers nowadays.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        answered Aug 18 at 1:39


























        community wiki





        Yly












        • 3




          $begingroup$
          A recent result: arxiv.org/abs/1406.4088
          $endgroup$
          – Count Iblis
          Aug 18 at 2:16










        • $begingroup$
          Here's a reference to Ken Wilson's comments (see bottom of page 10): arxiv.org/pdf/1407.1855.pdf
          $endgroup$
          – Yly
          2 days ago














        • 3




          $begingroup$
          A recent result: arxiv.org/abs/1406.4088
          $endgroup$
          – Count Iblis
          Aug 18 at 2:16










        • $begingroup$
          Here's a reference to Ken Wilson's comments (see bottom of page 10): arxiv.org/pdf/1407.1855.pdf
          $endgroup$
          – Yly
          2 days ago








        3




        3




        $begingroup$
        A recent result: arxiv.org/abs/1406.4088
        $endgroup$
        – Count Iblis
        Aug 18 at 2:16




        $begingroup$
        A recent result: arxiv.org/abs/1406.4088
        $endgroup$
        – Count Iblis
        Aug 18 at 2:16












        $begingroup$
        Here's a reference to Ken Wilson's comments (see bottom of page 10): arxiv.org/pdf/1407.1855.pdf
        $endgroup$
        – Yly
        2 days ago




        $begingroup$
        Here's a reference to Ken Wilson's comments (see bottom of page 10): arxiv.org/pdf/1407.1855.pdf
        $endgroup$
        – Yly
        2 days ago











        21











        $begingroup$

        Packing problems come to mind, i.e. how to achieve the densest packing of some kind of geometric objects, such as spheres or dodecahedrons. The interesting thing is that this is not a discrete problem, as there are uncountably many irregular, non-periodic packings that need to be checked. Still, the original proof of the sphere packing problem managed to turn this into a finite number of linear programming problems which then could be solved on a computer.



        In theory you can use the same approach for objects other than spheres or in higher dimensions (and indeed people do), but in practice you reach a point quite soon, where there is simply not enough computing power to solve the resulting problems.






        share|cite|improve this answer











        $endgroup$




















          21











          $begingroup$

          Packing problems come to mind, i.e. how to achieve the densest packing of some kind of geometric objects, such as spheres or dodecahedrons. The interesting thing is that this is not a discrete problem, as there are uncountably many irregular, non-periodic packings that need to be checked. Still, the original proof of the sphere packing problem managed to turn this into a finite number of linear programming problems which then could be solved on a computer.



          In theory you can use the same approach for objects other than spheres or in higher dimensions (and indeed people do), but in practice you reach a point quite soon, where there is simply not enough computing power to solve the resulting problems.






          share|cite|improve this answer











          $endgroup$


















            21












            21








            21





            $begingroup$

            Packing problems come to mind, i.e. how to achieve the densest packing of some kind of geometric objects, such as spheres or dodecahedrons. The interesting thing is that this is not a discrete problem, as there are uncountably many irregular, non-periodic packings that need to be checked. Still, the original proof of the sphere packing problem managed to turn this into a finite number of linear programming problems which then could be solved on a computer.



            In theory you can use the same approach for objects other than spheres or in higher dimensions (and indeed people do), but in practice you reach a point quite soon, where there is simply not enough computing power to solve the resulting problems.






            share|cite|improve this answer











            $endgroup$



            Packing problems come to mind, i.e. how to achieve the densest packing of some kind of geometric objects, such as spheres or dodecahedrons. The interesting thing is that this is not a discrete problem, as there are uncountably many irregular, non-periodic packings that need to be checked. Still, the original proof of the sphere packing problem managed to turn this into a finite number of linear programming problems which then could be solved on a computer.



            In theory you can use the same approach for objects other than spheres or in higher dimensions (and indeed people do), but in practice you reach a point quite soon, where there is simply not enough computing power to solve the resulting problems.







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            answered Aug 17 at 7:47


























            community wiki





            mlk



























                14











                $begingroup$

                Is $e^{e^{e^{79}}}$ an integer? See this question for some background. Many other problems of this type are also technically unsolved, although the answer is almost definitely "no". This can be verified by a finite computation, but the sheer size of the numbers involved means that this is not feasible at the moment.



                Note: as pointed out by @ruakh, if $e^{e^{e^{79}}}$ were, in fact, an integer, then a naïve finite computation would not be able to resolve the question. [Of course, this seems highly unlikely, but it is not known to be false absent proof.]






                share|cite|improve this answer











                $endgroup$















                • $begingroup$
                  Nice to know about this. Thanks for pointing it out
                  $endgroup$
                  – StackUpPhysics
                  Aug 18 at 13:29










                • $begingroup$
                  This answer is thought-provoking (+1), but as far as I can tell it's not actually correct: if the answer is "no" then that could be verified by a finite computation that approximated it closely enough to rule out the neighboring integers; but if the answer is "yes" then there's no obvious computational way to prove it. All we could show is that it's within ε of an integer for ridiculously small values of ε. (In fact, this very issue was the motivation for the question you link to: see https://math.stackexchange.com/a/13052/19345.)
                  $endgroup$
                  – ruakh
                  yesterday












                • $begingroup$
                  @ruakh Wow, I hadn't thought of that. You're right, I will edit the answer to reflect that later.
                  $endgroup$
                  – YiFan
                  yesterday
















                14











                $begingroup$

                Is $e^{e^{e^{79}}}$ an integer? See this question for some background. Many other problems of this type are also technically unsolved, although the answer is almost definitely "no". This can be verified by a finite computation, but the sheer size of the numbers involved means that this is not feasible at the moment.



                Note: as pointed out by @ruakh, if $e^{e^{e^{79}}}$ were, in fact, an integer, then a naïve finite computation would not be able to resolve the question. [Of course, this seems highly unlikely, but it is not known to be false absent proof.]






                share|cite|improve this answer











                $endgroup$















                • $begingroup$
                  Nice to know about this. Thanks for pointing it out
                  $endgroup$
                  – StackUpPhysics
                  Aug 18 at 13:29










                • $begingroup$
                  This answer is thought-provoking (+1), but as far as I can tell it's not actually correct: if the answer is "no" then that could be verified by a finite computation that approximated it closely enough to rule out the neighboring integers; but if the answer is "yes" then there's no obvious computational way to prove it. All we could show is that it's within ε of an integer for ridiculously small values of ε. (In fact, this very issue was the motivation for the question you link to: see https://math.stackexchange.com/a/13052/19345.)
                  $endgroup$
                  – ruakh
                  yesterday












                • $begingroup$
                  @ruakh Wow, I hadn't thought of that. You're right, I will edit the answer to reflect that later.
                  $endgroup$
                  – YiFan
                  yesterday














                14












                14








                14





                $begingroup$

                Is $e^{e^{e^{79}}}$ an integer? See this question for some background. Many other problems of this type are also technically unsolved, although the answer is almost definitely "no". This can be verified by a finite computation, but the sheer size of the numbers involved means that this is not feasible at the moment.



                Note: as pointed out by @ruakh, if $e^{e^{e^{79}}}$ were, in fact, an integer, then a naïve finite computation would not be able to resolve the question. [Of course, this seems highly unlikely, but it is not known to be false absent proof.]






                share|cite|improve this answer











                $endgroup$



                Is $e^{e^{e^{79}}}$ an integer? See this question for some background. Many other problems of this type are also technically unsolved, although the answer is almost definitely "no". This can be verified by a finite computation, but the sheer size of the numbers involved means that this is not feasible at the moment.



                Note: as pointed out by @ruakh, if $e^{e^{e^{79}}}$ were, in fact, an integer, then a naïve finite computation would not be able to resolve the question. [Of course, this seems highly unlikely, but it is not known to be false absent proof.]







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited yesterday


























                community wiki





                2 revs
                YiFan
















                • $begingroup$
                  Nice to know about this. Thanks for pointing it out
                  $endgroup$
                  – StackUpPhysics
                  Aug 18 at 13:29










                • $begingroup$
                  This answer is thought-provoking (+1), but as far as I can tell it's not actually correct: if the answer is "no" then that could be verified by a finite computation that approximated it closely enough to rule out the neighboring integers; but if the answer is "yes" then there's no obvious computational way to prove it. All we could show is that it's within ε of an integer for ridiculously small values of ε. (In fact, this very issue was the motivation for the question you link to: see https://math.stackexchange.com/a/13052/19345.)
                  $endgroup$
                  – ruakh
                  yesterday












                • $begingroup$
                  @ruakh Wow, I hadn't thought of that. You're right, I will edit the answer to reflect that later.
                  $endgroup$
                  – YiFan
                  yesterday


















                • $begingroup$
                  Nice to know about this. Thanks for pointing it out
                  $endgroup$
                  – StackUpPhysics
                  Aug 18 at 13:29










                • $begingroup$
                  This answer is thought-provoking (+1), but as far as I can tell it's not actually correct: if the answer is "no" then that could be verified by a finite computation that approximated it closely enough to rule out the neighboring integers; but if the answer is "yes" then there's no obvious computational way to prove it. All we could show is that it's within ε of an integer for ridiculously small values of ε. (In fact, this very issue was the motivation for the question you link to: see https://math.stackexchange.com/a/13052/19345.)
                  $endgroup$
                  – ruakh
                  yesterday












                • $begingroup$
                  @ruakh Wow, I hadn't thought of that. You're right, I will edit the answer to reflect that later.
                  $endgroup$
                  – YiFan
                  yesterday
















                $begingroup$
                Nice to know about this. Thanks for pointing it out
                $endgroup$
                – StackUpPhysics
                Aug 18 at 13:29




                $begingroup$
                Nice to know about this. Thanks for pointing it out
                $endgroup$
                – StackUpPhysics
                Aug 18 at 13:29












                $begingroup$
                This answer is thought-provoking (+1), but as far as I can tell it's not actually correct: if the answer is "no" then that could be verified by a finite computation that approximated it closely enough to rule out the neighboring integers; but if the answer is "yes" then there's no obvious computational way to prove it. All we could show is that it's within ε of an integer for ridiculously small values of ε. (In fact, this very issue was the motivation for the question you link to: see https://math.stackexchange.com/a/13052/19345.)
                $endgroup$
                – ruakh
                yesterday






                $begingroup$
                This answer is thought-provoking (+1), but as far as I can tell it's not actually correct: if the answer is "no" then that could be verified by a finite computation that approximated it closely enough to rule out the neighboring integers; but if the answer is "yes" then there's no obvious computational way to prove it. All we could show is that it's within ε of an integer for ridiculously small values of ε. (In fact, this very issue was the motivation for the question you link to: see https://math.stackexchange.com/a/13052/19345.)
                $endgroup$
                – ruakh
                yesterday














                $begingroup$
                @ruakh Wow, I hadn't thought of that. You're right, I will edit the answer to reflect that later.
                $endgroup$
                – YiFan
                yesterday




                $begingroup$
                @ruakh Wow, I hadn't thought of that. You're right, I will edit the answer to reflect that later.
                $endgroup$
                – YiFan
                yesterday











                11











                $begingroup$

                It is strongly believed that the second Hardy-Littlewood conjecture is false, because it contradicts the first Hardy-Littlewood conjecture, which has the backing of not only the probabilistic heuristic but also a lot of recent work. The second link even states that if the first conjecture (also called the prime $k$-tuples conjecture) holds, then there are in fact infinitely many positive integers $x$ such that $π(x+3159)-π(x) = 447 > 446 = π(3159)$. This is obviously something that can be verified with sufficient computational power (simply test every positive integer $x$ until you find one that satisfies the desired inequality), but clearly it has not been done yet otherwise we would have heard news of it!






                share|cite|improve this answer











                $endgroup$















                • $begingroup$
                  Interesting to get to know about this. Haven't heard about this conjecture before
                  $endgroup$
                  – StackUpPhysics
                  Aug 18 at 13:28










                • $begingroup$
                  I don't think this answers the question. It's structurally very similar to disproving the Riemann hypothesis, which is explicitly given as an example of something the OP doesn't want.
                  $endgroup$
                  – Brady Gilg
                  2 days ago










                • $begingroup$
                  @BradyGilg: Note that I answered the question before it was significantly changed. Besides, this is quite different from disproving RH because people believe RH is true (so it shouldn't be disprovable) whereas people believe that the conjecture stated in my post is true and hence provable by a finite computation.
                  $endgroup$
                  – user21820
                  2 days ago
















                11











                $begingroup$

                It is strongly believed that the second Hardy-Littlewood conjecture is false, because it contradicts the first Hardy-Littlewood conjecture, which has the backing of not only the probabilistic heuristic but also a lot of recent work. The second link even states that if the first conjecture (also called the prime $k$-tuples conjecture) holds, then there are in fact infinitely many positive integers $x$ such that $π(x+3159)-π(x) = 447 > 446 = π(3159)$. This is obviously something that can be verified with sufficient computational power (simply test every positive integer $x$ until you find one that satisfies the desired inequality), but clearly it has not been done yet otherwise we would have heard news of it!






                share|cite|improve this answer











                $endgroup$















                • $begingroup$
                  Interesting to get to know about this. Haven't heard about this conjecture before
                  $endgroup$
                  – StackUpPhysics
                  Aug 18 at 13:28










                • $begingroup$
                  I don't think this answers the question. It's structurally very similar to disproving the Riemann hypothesis, which is explicitly given as an example of something the OP doesn't want.
                  $endgroup$
                  – Brady Gilg
                  2 days ago










                • $begingroup$
                  @BradyGilg: Note that I answered the question before it was significantly changed. Besides, this is quite different from disproving RH because people believe RH is true (so it shouldn't be disprovable) whereas people believe that the conjecture stated in my post is true and hence provable by a finite computation.
                  $endgroup$
                  – user21820
                  2 days ago














                11












                11








                11





                $begingroup$

                It is strongly believed that the second Hardy-Littlewood conjecture is false, because it contradicts the first Hardy-Littlewood conjecture, which has the backing of not only the probabilistic heuristic but also a lot of recent work. The second link even states that if the first conjecture (also called the prime $k$-tuples conjecture) holds, then there are in fact infinitely many positive integers $x$ such that $π(x+3159)-π(x) = 447 > 446 = π(3159)$. This is obviously something that can be verified with sufficient computational power (simply test every positive integer $x$ until you find one that satisfies the desired inequality), but clearly it has not been done yet otherwise we would have heard news of it!






                share|cite|improve this answer











                $endgroup$



                It is strongly believed that the second Hardy-Littlewood conjecture is false, because it contradicts the first Hardy-Littlewood conjecture, which has the backing of not only the probabilistic heuristic but also a lot of recent work. The second link even states that if the first conjecture (also called the prime $k$-tuples conjecture) holds, then there are in fact infinitely many positive integers $x$ such that $π(x+3159)-π(x) = 447 > 446 = π(3159)$. This is obviously something that can be verified with sufficient computational power (simply test every positive integer $x$ until you find one that satisfies the desired inequality), but clearly it has not been done yet otherwise we would have heard news of it!







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                answered Aug 18 at 3:16


























                community wiki





                user21820
















                • $begingroup$
                  Interesting to get to know about this. Haven't heard about this conjecture before
                  $endgroup$
                  – StackUpPhysics
                  Aug 18 at 13:28










                • $begingroup$
                  I don't think this answers the question. It's structurally very similar to disproving the Riemann hypothesis, which is explicitly given as an example of something the OP doesn't want.
                  $endgroup$
                  – Brady Gilg
                  2 days ago










                • $begingroup$
                  @BradyGilg: Note that I answered the question before it was significantly changed. Besides, this is quite different from disproving RH because people believe RH is true (so it shouldn't be disprovable) whereas people believe that the conjecture stated in my post is true and hence provable by a finite computation.
                  $endgroup$
                  – user21820
                  2 days ago


















                • $begingroup$
                  Interesting to get to know about this. Haven't heard about this conjecture before
                  $endgroup$
                  – StackUpPhysics
                  Aug 18 at 13:28










                • $begingroup$
                  I don't think this answers the question. It's structurally very similar to disproving the Riemann hypothesis, which is explicitly given as an example of something the OP doesn't want.
                  $endgroup$
                  – Brady Gilg
                  2 days ago










                • $begingroup$
                  @BradyGilg: Note that I answered the question before it was significantly changed. Besides, this is quite different from disproving RH because people believe RH is true (so it shouldn't be disprovable) whereas people believe that the conjecture stated in my post is true and hence provable by a finite computation.
                  $endgroup$
                  – user21820
                  2 days ago
















                $begingroup$
                Interesting to get to know about this. Haven't heard about this conjecture before
                $endgroup$
                – StackUpPhysics
                Aug 18 at 13:28




                $begingroup$
                Interesting to get to know about this. Haven't heard about this conjecture before
                $endgroup$
                – StackUpPhysics
                Aug 18 at 13:28












                $begingroup$
                I don't think this answers the question. It's structurally very similar to disproving the Riemann hypothesis, which is explicitly given as an example of something the OP doesn't want.
                $endgroup$
                – Brady Gilg
                2 days ago




                $begingroup$
                I don't think this answers the question. It's structurally very similar to disproving the Riemann hypothesis, which is explicitly given as an example of something the OP doesn't want.
                $endgroup$
                – Brady Gilg
                2 days ago












                $begingroup$
                @BradyGilg: Note that I answered the question before it was significantly changed. Besides, this is quite different from disproving RH because people believe RH is true (so it shouldn't be disprovable) whereas people believe that the conjecture stated in my post is true and hence provable by a finite computation.
                $endgroup$
                – user21820
                2 days ago




                $begingroup$
                @BradyGilg: Note that I answered the question before it was significantly changed. Besides, this is quite different from disproving RH because people believe RH is true (so it shouldn't be disprovable) whereas people believe that the conjecture stated in my post is true and hence provable by a finite computation.
                $endgroup$
                – user21820
                2 days ago











                8











                $begingroup$

                Optimal sorting networks
                for $n>10$.




                For small, fixed numbers of inputs n, optimal sorting networks can be
                constructed, with either minimal depth (for maximally parallel
                execution) or minimal size (number of comparators)... The following
                table summarizes the known optimality results:




                $$ begin{array}{l|ccccccccccccccccc|} hline n & 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17 \ hline text{Depth} & 0& 1& 3& 3& 5& 5& 6& 6& 7& 7& 8& 8& 9& 9& 9& 9& 10 \ hline text{Size, upper bound} & 0& 1& 3& 5& 9& 12& 16& 19& 25& 29& 35& 39& 45& 51& 56& 60& 71 \ hline text{Size, lower bound (if different)} & & & & & & & & & & & 33& 37& 41& 45& 49& 53& 58 \ hline end{array} $$






                share|cite|improve this answer











                $endgroup$











                • 1




                  $begingroup$
                  can you elaborate in the answer?
                  $endgroup$
                  – Kai
                  Aug 18 at 17:15










                • $begingroup$
                  @ Kai : updated
                  $endgroup$
                  – g.kov
                  Aug 18 at 18:50
















                8











                $begingroup$

                Optimal sorting networks
                for $n>10$.




                For small, fixed numbers of inputs n, optimal sorting networks can be
                constructed, with either minimal depth (for maximally parallel
                execution) or minimal size (number of comparators)... The following
                table summarizes the known optimality results:




                $$ begin{array}{l|ccccccccccccccccc|} hline n & 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17 \ hline text{Depth} & 0& 1& 3& 3& 5& 5& 6& 6& 7& 7& 8& 8& 9& 9& 9& 9& 10 \ hline text{Size, upper bound} & 0& 1& 3& 5& 9& 12& 16& 19& 25& 29& 35& 39& 45& 51& 56& 60& 71 \ hline text{Size, lower bound (if different)} & & & & & & & & & & & 33& 37& 41& 45& 49& 53& 58 \ hline end{array} $$






                share|cite|improve this answer











                $endgroup$











                • 1




                  $begingroup$
                  can you elaborate in the answer?
                  $endgroup$
                  – Kai
                  Aug 18 at 17:15










                • $begingroup$
                  @ Kai : updated
                  $endgroup$
                  – g.kov
                  Aug 18 at 18:50














                8












                8








                8





                $begingroup$

                Optimal sorting networks
                for $n>10$.




                For small, fixed numbers of inputs n, optimal sorting networks can be
                constructed, with either minimal depth (for maximally parallel
                execution) or minimal size (number of comparators)... The following
                table summarizes the known optimality results:




                $$ begin{array}{l|ccccccccccccccccc|} hline n & 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17 \ hline text{Depth} & 0& 1& 3& 3& 5& 5& 6& 6& 7& 7& 8& 8& 9& 9& 9& 9& 10 \ hline text{Size, upper bound} & 0& 1& 3& 5& 9& 12& 16& 19& 25& 29& 35& 39& 45& 51& 56& 60& 71 \ hline text{Size, lower bound (if different)} & & & & & & & & & & & 33& 37& 41& 45& 49& 53& 58 \ hline end{array} $$






                share|cite|improve this answer











                $endgroup$



                Optimal sorting networks
                for $n>10$.




                For small, fixed numbers of inputs n, optimal sorting networks can be
                constructed, with either minimal depth (for maximally parallel
                execution) or minimal size (number of comparators)... The following
                table summarizes the known optimality results:




                $$ begin{array}{l|ccccccccccccccccc|} hline n & 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17 \ hline text{Depth} & 0& 1& 3& 3& 5& 5& 6& 6& 7& 7& 8& 8& 9& 9& 9& 9& 10 \ hline text{Size, upper bound} & 0& 1& 3& 5& 9& 12& 16& 19& 25& 29& 35& 39& 45& 51& 56& 60& 71 \ hline text{Size, lower bound (if different)} & & & & & & & & & & & 33& 37& 41& 45& 49& 53& 58 \ hline end{array} $$







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited Aug 18 at 18:48


























                community wiki





                2 revs
                g.kov












                • 1




                  $begingroup$
                  can you elaborate in the answer?
                  $endgroup$
                  – Kai
                  Aug 18 at 17:15










                • $begingroup$
                  @ Kai : updated
                  $endgroup$
                  – g.kov
                  Aug 18 at 18:50














                • 1




                  $begingroup$
                  can you elaborate in the answer?
                  $endgroup$
                  – Kai
                  Aug 18 at 17:15










                • $begingroup$
                  @ Kai : updated
                  $endgroup$
                  – g.kov
                  Aug 18 at 18:50








                1




                1




                $begingroup$
                can you elaborate in the answer?
                $endgroup$
                – Kai
                Aug 18 at 17:15




                $begingroup$
                can you elaborate in the answer?
                $endgroup$
                – Kai
                Aug 18 at 17:15












                $begingroup$
                @ Kai : updated
                $endgroup$
                – g.kov
                Aug 18 at 18:50




                $begingroup$
                @ Kai : updated
                $endgroup$
                – g.kov
                Aug 18 at 18:50











                7











                $begingroup$

                Euler's conjecture that it takes $n$ $n$th powers to sum to an $n$ power is true for $n=3$ but proven false for $n=4,5$, for example,



                $$27^5+ 84^5+110^5+ 133^5= 144^5qquadtext{(found in 1966)}$$
                $$95800^4 + 217519^4 + 414560^4 = 422481^4qquadtext{(found in 1988)}$$



                but nobody knows if it is false for any or all $ngeq6$. There are heuristics that suggest,



                $$x_1^6+x_2^6+dots+x_5^6 = z^6$$



                has positive solutions as well and a fast enough computer might find it. For the moment, such computational power is not available to individuals.






                share|cite|improve this answer











                $endgroup$











                • 4




                  $begingroup$
                  Interesting problem, but it does not seem to match: "Problems of which we know that they can be solved with a finite (but very long) computation? " (my emphasis).
                  $endgroup$
                  – quid
                  Aug 18 at 11:32
















                7











                $begingroup$

                Euler's conjecture that it takes $n$ $n$th powers to sum to an $n$ power is true for $n=3$ but proven false for $n=4,5$, for example,



                $$27^5+ 84^5+110^5+ 133^5= 144^5qquadtext{(found in 1966)}$$
                $$95800^4 + 217519^4 + 414560^4 = 422481^4qquadtext{(found in 1988)}$$



                but nobody knows if it is false for any or all $ngeq6$. There are heuristics that suggest,



                $$x_1^6+x_2^6+dots+x_5^6 = z^6$$



                has positive solutions as well and a fast enough computer might find it. For the moment, such computational power is not available to individuals.






                share|cite|improve this answer











                $endgroup$











                • 4




                  $begingroup$
                  Interesting problem, but it does not seem to match: "Problems of which we know that they can be solved with a finite (but very long) computation? " (my emphasis).
                  $endgroup$
                  – quid
                  Aug 18 at 11:32














                7












                7








                7





                $begingroup$

                Euler's conjecture that it takes $n$ $n$th powers to sum to an $n$ power is true for $n=3$ but proven false for $n=4,5$, for example,



                $$27^5+ 84^5+110^5+ 133^5= 144^5qquadtext{(found in 1966)}$$
                $$95800^4 + 217519^4 + 414560^4 = 422481^4qquadtext{(found in 1988)}$$



                but nobody knows if it is false for any or all $ngeq6$. There are heuristics that suggest,



                $$x_1^6+x_2^6+dots+x_5^6 = z^6$$



                has positive solutions as well and a fast enough computer might find it. For the moment, such computational power is not available to individuals.






                share|cite|improve this answer











                $endgroup$



                Euler's conjecture that it takes $n$ $n$th powers to sum to an $n$ power is true for $n=3$ but proven false for $n=4,5$, for example,



                $$27^5+ 84^5+110^5+ 133^5= 144^5qquadtext{(found in 1966)}$$
                $$95800^4 + 217519^4 + 414560^4 = 422481^4qquadtext{(found in 1988)}$$



                but nobody knows if it is false for any or all $ngeq6$. There are heuristics that suggest,



                $$x_1^6+x_2^6+dots+x_5^6 = z^6$$



                has positive solutions as well and a fast enough computer might find it. For the moment, such computational power is not available to individuals.







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                answered Aug 18 at 4:21


























                community wiki





                Tito Piezas III












                • 4




                  $begingroup$
                  Interesting problem, but it does not seem to match: "Problems of which we know that they can be solved with a finite (but very long) computation? " (my emphasis).
                  $endgroup$
                  – quid
                  Aug 18 at 11:32














                • 4




                  $begingroup$
                  Interesting problem, but it does not seem to match: "Problems of which we know that they can be solved with a finite (but very long) computation? " (my emphasis).
                  $endgroup$
                  – quid
                  Aug 18 at 11:32








                4




                4




                $begingroup$
                Interesting problem, but it does not seem to match: "Problems of which we know that they can be solved with a finite (but very long) computation? " (my emphasis).
                $endgroup$
                – quid
                Aug 18 at 11:32




                $begingroup$
                Interesting problem, but it does not seem to match: "Problems of which we know that they can be solved with a finite (but very long) computation? " (my emphasis).
                $endgroup$
                – quid
                Aug 18 at 11:32











                6











                $begingroup$

                The order of every finite projective plane is a prime power. If this is false, a counterexample can be constructed by exhaustive search of all non-prime powers in increasing order. This has been done by hand for $n=6$ and by computer for $n=10$, but as far as I know, $n=12$ is still out of reach, or at least, it hasn't been done.






                share|cite|improve this answer











                $endgroup$











                • 4




                  $begingroup$
                  My understanding of the question suggests that this isn't an example unless there's some upper bound at which point we can stop. My interpretation of the question is the problems need to be computationally decidable, not semidecidable. Otherwise, we could say of any (formal) theorem that "if it's 'true', then we can enumerate proofs until we find its proof". Of course, you could say the $n=12$ case is decidable, but it still seems to miss the spirit of the question unless there's something special about this case. I could just as well ask if a theorem has a proof of size at most $N$.
                  $endgroup$
                  – Derek Elkins
                  Aug 18 at 1:57










                • $begingroup$
                  An alternative conjecture used to be that a finite projective plane exists for every order not ruled out by the Bruck-Ryser theorem. Orders 6 and 14 are so ruled out, but orders 10 and 12 are not. This conjecture is, of course, dead now that a plane of order 10 has been ruled out by computational means. But I think many people still would like to know whether a plane of order 12 exists.
                  $endgroup$
                  – Will Orrick
                  Aug 18 at 12:23












                • $begingroup$
                  Is it believed that there is a finite projective plane with order not a prime power?
                  $endgroup$
                  – user21820
                  2 days ago










                • $begingroup$
                  @user21820 I'm not a worker in the field, so I can't really say. In 1995, Gary Mullen suggested it as a candidate for "the next Fermat problem" Unfortunately, Springer doesn't make the whole article available publicly. The MOLS problem he discusses is equivalent to the finite projective plane problem. See pi.math.cornell.edu/~web4520/CG9-0.pdf
                  $endgroup$
                  – saulspatz
                  2 days ago












                • $begingroup$
                  Thanks! Upon accessing the full paper, it says that: Kirkman established the existence of projective planes of prime power order around 1850, and Bose showed the equivalence of having $n - 1$ MOLS of order $n$ and having a projective plane of order $n$. Bruck and Ryser proved that if $n$ is $1$ or $2$ mod $4$ and the square-free part of $n$ has at least one prime factor of the form $4k + 3$, then there cannot be $n-1$ MOLS of order $n$. This result was proven using numerous number-theoretic techniques, including Lagrange's 4-square theorem.
                  $endgroup$
                  – user21820
                  2 days ago
















                6











                $begingroup$

                The order of every finite projective plane is a prime power. If this is false, a counterexample can be constructed by exhaustive search of all non-prime powers in increasing order. This has been done by hand for $n=6$ and by computer for $n=10$, but as far as I know, $n=12$ is still out of reach, or at least, it hasn't been done.






                share|cite|improve this answer











                $endgroup$











                • 4




                  $begingroup$
                  My understanding of the question suggests that this isn't an example unless there's some upper bound at which point we can stop. My interpretation of the question is the problems need to be computationally decidable, not semidecidable. Otherwise, we could say of any (formal) theorem that "if it's 'true', then we can enumerate proofs until we find its proof". Of course, you could say the $n=12$ case is decidable, but it still seems to miss the spirit of the question unless there's something special about this case. I could just as well ask if a theorem has a proof of size at most $N$.
                  $endgroup$
                  – Derek Elkins
                  Aug 18 at 1:57










                • $begingroup$
                  An alternative conjecture used to be that a finite projective plane exists for every order not ruled out by the Bruck-Ryser theorem. Orders 6 and 14 are so ruled out, but orders 10 and 12 are not. This conjecture is, of course, dead now that a plane of order 10 has been ruled out by computational means. But I think many people still would like to know whether a plane of order 12 exists.
                  $endgroup$
                  – Will Orrick
                  Aug 18 at 12:23












                • $begingroup$
                  Is it believed that there is a finite projective plane with order not a prime power?
                  $endgroup$
                  – user21820
                  2 days ago










                • $begingroup$
                  @user21820 I'm not a worker in the field, so I can't really say. In 1995, Gary Mullen suggested it as a candidate for "the next Fermat problem" Unfortunately, Springer doesn't make the whole article available publicly. The MOLS problem he discusses is equivalent to the finite projective plane problem. See pi.math.cornell.edu/~web4520/CG9-0.pdf
                  $endgroup$
                  – saulspatz
                  2 days ago












                • $begingroup$
                  Thanks! Upon accessing the full paper, it says that: Kirkman established the existence of projective planes of prime power order around 1850, and Bose showed the equivalence of having $n - 1$ MOLS of order $n$ and having a projective plane of order $n$. Bruck and Ryser proved that if $n$ is $1$ or $2$ mod $4$ and the square-free part of $n$ has at least one prime factor of the form $4k + 3$, then there cannot be $n-1$ MOLS of order $n$. This result was proven using numerous number-theoretic techniques, including Lagrange's 4-square theorem.
                  $endgroup$
                  – user21820
                  2 days ago














                6












                6








                6





                $begingroup$

                The order of every finite projective plane is a prime power. If this is false, a counterexample can be constructed by exhaustive search of all non-prime powers in increasing order. This has been done by hand for $n=6$ and by computer for $n=10$, but as far as I know, $n=12$ is still out of reach, or at least, it hasn't been done.






                share|cite|improve this answer











                $endgroup$



                The order of every finite projective plane is a prime power. If this is false, a counterexample can be constructed by exhaustive search of all non-prime powers in increasing order. This has been done by hand for $n=6$ and by computer for $n=10$, but as far as I know, $n=12$ is still out of reach, or at least, it hasn't been done.







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                answered Aug 17 at 18:41


























                community wiki





                saulspatz












                • 4




                  $begingroup$
                  My understanding of the question suggests that this isn't an example unless there's some upper bound at which point we can stop. My interpretation of the question is the problems need to be computationally decidable, not semidecidable. Otherwise, we could say of any (formal) theorem that "if it's 'true', then we can enumerate proofs until we find its proof". Of course, you could say the $n=12$ case is decidable, but it still seems to miss the spirit of the question unless there's something special about this case. I could just as well ask if a theorem has a proof of size at most $N$.
                  $endgroup$
                  – Derek Elkins
                  Aug 18 at 1:57










                • $begingroup$
                  An alternative conjecture used to be that a finite projective plane exists for every order not ruled out by the Bruck-Ryser theorem. Orders 6 and 14 are so ruled out, but orders 10 and 12 are not. This conjecture is, of course, dead now that a plane of order 10 has been ruled out by computational means. But I think many people still would like to know whether a plane of order 12 exists.
                  $endgroup$
                  – Will Orrick
                  Aug 18 at 12:23












                • $begingroup$
                  Is it believed that there is a finite projective plane with order not a prime power?
                  $endgroup$
                  – user21820
                  2 days ago










                • $begingroup$
                  @user21820 I'm not a worker in the field, so I can't really say. In 1995, Gary Mullen suggested it as a candidate for "the next Fermat problem" Unfortunately, Springer doesn't make the whole article available publicly. The MOLS problem he discusses is equivalent to the finite projective plane problem. See pi.math.cornell.edu/~web4520/CG9-0.pdf
                  $endgroup$
                  – saulspatz
                  2 days ago












                • $begingroup$
                  Thanks! Upon accessing the full paper, it says that: Kirkman established the existence of projective planes of prime power order around 1850, and Bose showed the equivalence of having $n - 1$ MOLS of order $n$ and having a projective plane of order $n$. Bruck and Ryser proved that if $n$ is $1$ or $2$ mod $4$ and the square-free part of $n$ has at least one prime factor of the form $4k + 3$, then there cannot be $n-1$ MOLS of order $n$. This result was proven using numerous number-theoretic techniques, including Lagrange's 4-square theorem.
                  $endgroup$
                  – user21820
                  2 days ago














                • 4




                  $begingroup$
                  My understanding of the question suggests that this isn't an example unless there's some upper bound at which point we can stop. My interpretation of the question is the problems need to be computationally decidable, not semidecidable. Otherwise, we could say of any (formal) theorem that "if it's 'true', then we can enumerate proofs until we find its proof". Of course, you could say the $n=12$ case is decidable, but it still seems to miss the spirit of the question unless there's something special about this case. I could just as well ask if a theorem has a proof of size at most $N$.
                  $endgroup$
                  – Derek Elkins
                  Aug 18 at 1:57










                • $begingroup$
                  An alternative conjecture used to be that a finite projective plane exists for every order not ruled out by the Bruck-Ryser theorem. Orders 6 and 14 are so ruled out, but orders 10 and 12 are not. This conjecture is, of course, dead now that a plane of order 10 has been ruled out by computational means. But I think many people still would like to know whether a plane of order 12 exists.
                  $endgroup$
                  – Will Orrick
                  Aug 18 at 12:23












                • $begingroup$
                  Is it believed that there is a finite projective plane with order not a prime power?
                  $endgroup$
                  – user21820
                  2 days ago










                • $begingroup$
                  @user21820 I'm not a worker in the field, so I can't really say. In 1995, Gary Mullen suggested it as a candidate for "the next Fermat problem" Unfortunately, Springer doesn't make the whole article available publicly. The MOLS problem he discusses is equivalent to the finite projective plane problem. See pi.math.cornell.edu/~web4520/CG9-0.pdf
                  $endgroup$
                  – saulspatz
                  2 days ago












                • $begingroup$
                  Thanks! Upon accessing the full paper, it says that: Kirkman established the existence of projective planes of prime power order around 1850, and Bose showed the equivalence of having $n - 1$ MOLS of order $n$ and having a projective plane of order $n$. Bruck and Ryser proved that if $n$ is $1$ or $2$ mod $4$ and the square-free part of $n$ has at least one prime factor of the form $4k + 3$, then there cannot be $n-1$ MOLS of order $n$. This result was proven using numerous number-theoretic techniques, including Lagrange's 4-square theorem.
                  $endgroup$
                  – user21820
                  2 days ago








                4




                4




                $begingroup$
                My understanding of the question suggests that this isn't an example unless there's some upper bound at which point we can stop. My interpretation of the question is the problems need to be computationally decidable, not semidecidable. Otherwise, we could say of any (formal) theorem that "if it's 'true', then we can enumerate proofs until we find its proof". Of course, you could say the $n=12$ case is decidable, but it still seems to miss the spirit of the question unless there's something special about this case. I could just as well ask if a theorem has a proof of size at most $N$.
                $endgroup$
                – Derek Elkins
                Aug 18 at 1:57




                $begingroup$
                My understanding of the question suggests that this isn't an example unless there's some upper bound at which point we can stop. My interpretation of the question is the problems need to be computationally decidable, not semidecidable. Otherwise, we could say of any (formal) theorem that "if it's 'true', then we can enumerate proofs until we find its proof". Of course, you could say the $n=12$ case is decidable, but it still seems to miss the spirit of the question unless there's something special about this case. I could just as well ask if a theorem has a proof of size at most $N$.
                $endgroup$
                – Derek Elkins
                Aug 18 at 1:57












                $begingroup$
                An alternative conjecture used to be that a finite projective plane exists for every order not ruled out by the Bruck-Ryser theorem. Orders 6 and 14 are so ruled out, but orders 10 and 12 are not. This conjecture is, of course, dead now that a plane of order 10 has been ruled out by computational means. But I think many people still would like to know whether a plane of order 12 exists.
                $endgroup$
                – Will Orrick
                Aug 18 at 12:23






                $begingroup$
                An alternative conjecture used to be that a finite projective plane exists for every order not ruled out by the Bruck-Ryser theorem. Orders 6 and 14 are so ruled out, but orders 10 and 12 are not. This conjecture is, of course, dead now that a plane of order 10 has been ruled out by computational means. But I think many people still would like to know whether a plane of order 12 exists.
                $endgroup$
                – Will Orrick
                Aug 18 at 12:23














                $begingroup$
                Is it believed that there is a finite projective plane with order not a prime power?
                $endgroup$
                – user21820
                2 days ago




                $begingroup$
                Is it believed that there is a finite projective plane with order not a prime power?
                $endgroup$
                – user21820
                2 days ago












                $begingroup$
                @user21820 I'm not a worker in the field, so I can't really say. In 1995, Gary Mullen suggested it as a candidate for "the next Fermat problem" Unfortunately, Springer doesn't make the whole article available publicly. The MOLS problem he discusses is equivalent to the finite projective plane problem. See pi.math.cornell.edu/~web4520/CG9-0.pdf
                $endgroup$
                – saulspatz
                2 days ago






                $begingroup$
                @user21820 I'm not a worker in the field, so I can't really say. In 1995, Gary Mullen suggested it as a candidate for "the next Fermat problem" Unfortunately, Springer doesn't make the whole article available publicly. The MOLS problem he discusses is equivalent to the finite projective plane problem. See pi.math.cornell.edu/~web4520/CG9-0.pdf
                $endgroup$
                – saulspatz
                2 days ago














                $begingroup$
                Thanks! Upon accessing the full paper, it says that: Kirkman established the existence of projective planes of prime power order around 1850, and Bose showed the equivalence of having $n - 1$ MOLS of order $n$ and having a projective plane of order $n$. Bruck and Ryser proved that if $n$ is $1$ or $2$ mod $4$ and the square-free part of $n$ has at least one prime factor of the form $4k + 3$, then there cannot be $n-1$ MOLS of order $n$. This result was proven using numerous number-theoretic techniques, including Lagrange's 4-square theorem.
                $endgroup$
                – user21820
                2 days ago




                $begingroup$
                Thanks! Upon accessing the full paper, it says that: Kirkman established the existence of projective planes of prime power order around 1850, and Bose showed the equivalence of having $n - 1$ MOLS of order $n$ and having a projective plane of order $n$. Bruck and Ryser proved that if $n$ is $1$ or $2$ mod $4$ and the square-free part of $n$ has at least one prime factor of the form $4k + 3$, then there cannot be $n-1$ MOLS of order $n$. This result was proven using numerous number-theoretic techniques, including Lagrange's 4-square theorem.
                $endgroup$
                – user21820
                2 days ago











                4











                $begingroup$

                Littlewood proved in 1914 that there exists a number $ninmathbb{N}$ (called Skewes' number) such that:



                $$
                pi(n) > operatorname{li}(n),
                $$



                where $pi(n)$ is the amount of primes below $n$ and $operatorname{li}(n)$ denotes the logarithmic integral $displaystyle int_0^n frac{dt}{ln t}$.



                It is conjectured that $n$ is a huge number, recent analysis suggests $napprox e^{727.951}$. Since then, researchers have worked to find lower and upper bounds for $n$. Currently it is held that:



                $$
                10^{19}<n<e^{727.951}.
                $$



                No such number has been found yet.






                share|cite|improve this answer











                $endgroup$















                • $begingroup$
                  Is it actually believed that Skewes' number is $approx e^{727}$? I thought I'd previously read that a crossing point is there but not necessarily the least crossing point (Skewes'), which as you point out could be as low as $10^{19}$
                  $endgroup$
                  – Jam
                  2 days ago


















                4











                $begingroup$

                Littlewood proved in 1914 that there exists a number $ninmathbb{N}$ (called Skewes' number) such that:



                $$
                pi(n) > operatorname{li}(n),
                $$



                where $pi(n)$ is the amount of primes below $n$ and $operatorname{li}(n)$ denotes the logarithmic integral $displaystyle int_0^n frac{dt}{ln t}$.



                It is conjectured that $n$ is a huge number, recent analysis suggests $napprox e^{727.951}$. Since then, researchers have worked to find lower and upper bounds for $n$. Currently it is held that:



                $$
                10^{19}<n<e^{727.951}.
                $$



                No such number has been found yet.






                share|cite|improve this answer











                $endgroup$















                • $begingroup$
                  Is it actually believed that Skewes' number is $approx e^{727}$? I thought I'd previously read that a crossing point is there but not necessarily the least crossing point (Skewes'), which as you point out could be as low as $10^{19}$
                  $endgroup$
                  – Jam
                  2 days ago
















                4












                4








                4





                $begingroup$

                Littlewood proved in 1914 that there exists a number $ninmathbb{N}$ (called Skewes' number) such that:



                $$
                pi(n) > operatorname{li}(n),
                $$



                where $pi(n)$ is the amount of primes below $n$ and $operatorname{li}(n)$ denotes the logarithmic integral $displaystyle int_0^n frac{dt}{ln t}$.



                It is conjectured that $n$ is a huge number, recent analysis suggests $napprox e^{727.951}$. Since then, researchers have worked to find lower and upper bounds for $n$. Currently it is held that:



                $$
                10^{19}<n<e^{727.951}.
                $$



                No such number has been found yet.






                share|cite|improve this answer











                $endgroup$



                Littlewood proved in 1914 that there exists a number $ninmathbb{N}$ (called Skewes' number) such that:



                $$
                pi(n) > operatorname{li}(n),
                $$



                where $pi(n)$ is the amount of primes below $n$ and $operatorname{li}(n)$ denotes the logarithmic integral $displaystyle int_0^n frac{dt}{ln t}$.



                It is conjectured that $n$ is a huge number, recent analysis suggests $napprox e^{727.951}$. Since then, researchers have worked to find lower and upper bounds for $n$. Currently it is held that:



                $$
                10^{19}<n<e^{727.951}.
                $$



                No such number has been found yet.







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited 2 days ago


























                community wiki





                2 revs, 2 users 97%
                Klangen
















                • $begingroup$
                  Is it actually believed that Skewes' number is $approx e^{727}$? I thought I'd previously read that a crossing point is there but not necessarily the least crossing point (Skewes'), which as you point out could be as low as $10^{19}$
                  $endgroup$
                  – Jam
                  2 days ago




















                • $begingroup$
                  Is it actually believed that Skewes' number is $approx e^{727}$? I thought I'd previously read that a crossing point is there but not necessarily the least crossing point (Skewes'), which as you point out could be as low as $10^{19}$
                  $endgroup$
                  – Jam
                  2 days ago


















                $begingroup$
                Is it actually believed that Skewes' number is $approx e^{727}$? I thought I'd previously read that a crossing point is there but not necessarily the least crossing point (Skewes'), which as you point out could be as low as $10^{19}$
                $endgroup$
                – Jam
                2 days ago






                $begingroup$
                Is it actually believed that Skewes' number is $approx e^{727}$? I thought I'd previously read that a crossing point is there but not necessarily the least crossing point (Skewes'), which as you point out could be as low as $10^{19}$
                $endgroup$
                – Jam
                2 days ago













                3











                $begingroup$

                There was the question: Are there m consecutive positive integers from k to k+m-1 which contain more primes than the m integers from 2 to m+1?



                The problem itself is unsolved, but there is a hypothesis with the twin-prime hypothesis as the simplest special case:



                Given n ≥ 2, and n integers $0 = k_1 < k_2 < ... < k_n$, and for every prime p ≤ n the set of remainders $k_i mod p$ has fewer than p elements, then there are infinitely many integers p such that $p + k_i$ is prime for every 1 ≤ i ≤ n.



                If there are n primes from 2 to 2+m-1, and we find $k_1$ to $k_{n+1}$ with $k_{n+1} ≤ m-1$, then the hypothesis is that there are infinitely many sequences of m consecutive integers containing n+1 primes.



                Finding such a sequence was quite hard but was done. I think there are sequences known that point to 5 more primes in m consecutive integers than in 2 to m-1, but beyond that it's limited by processing power (or by willingness to use that processing power).






                share|cite|improve this answer











                $endgroup$











                • 1




                  $begingroup$
                  The 1st paragraph is called the Hardy-Littlewood 2nd conjecture, the 3rd paragraph id called the Hardy-Littlewood 1st conjecture, see the answer from user21820.
                  $endgroup$
                  – Gerry Myerson
                  2 days ago
















                3











                $begingroup$

                There was the question: Are there m consecutive positive integers from k to k+m-1 which contain more primes than the m integers from 2 to m+1?



                The problem itself is unsolved, but there is a hypothesis with the twin-prime hypothesis as the simplest special case:



                Given n ≥ 2, and n integers $0 = k_1 < k_2 < ... < k_n$, and for every prime p ≤ n the set of remainders $k_i mod p$ has fewer than p elements, then there are infinitely many integers p such that $p + k_i$ is prime for every 1 ≤ i ≤ n.



                If there are n primes from 2 to 2+m-1, and we find $k_1$ to $k_{n+1}$ with $k_{n+1} ≤ m-1$, then the hypothesis is that there are infinitely many sequences of m consecutive integers containing n+1 primes.



                Finding such a sequence was quite hard but was done. I think there are sequences known that point to 5 more primes in m consecutive integers than in 2 to m-1, but beyond that it's limited by processing power (or by willingness to use that processing power).






                share|cite|improve this answer











                $endgroup$











                • 1




                  $begingroup$
                  The 1st paragraph is called the Hardy-Littlewood 2nd conjecture, the 3rd paragraph id called the Hardy-Littlewood 1st conjecture, see the answer from user21820.
                  $endgroup$
                  – Gerry Myerson
                  2 days ago














                3












                3








                3





                $begingroup$

                There was the question: Are there m consecutive positive integers from k to k+m-1 which contain more primes than the m integers from 2 to m+1?



                The problem itself is unsolved, but there is a hypothesis with the twin-prime hypothesis as the simplest special case:



                Given n ≥ 2, and n integers $0 = k_1 < k_2 < ... < k_n$, and for every prime p ≤ n the set of remainders $k_i mod p$ has fewer than p elements, then there are infinitely many integers p such that $p + k_i$ is prime for every 1 ≤ i ≤ n.



                If there are n primes from 2 to 2+m-1, and we find $k_1$ to $k_{n+1}$ with $k_{n+1} ≤ m-1$, then the hypothesis is that there are infinitely many sequences of m consecutive integers containing n+1 primes.



                Finding such a sequence was quite hard but was done. I think there are sequences known that point to 5 more primes in m consecutive integers than in 2 to m-1, but beyond that it's limited by processing power (or by willingness to use that processing power).






                share|cite|improve this answer











                $endgroup$



                There was the question: Are there m consecutive positive integers from k to k+m-1 which contain more primes than the m integers from 2 to m+1?



                The problem itself is unsolved, but there is a hypothesis with the twin-prime hypothesis as the simplest special case:



                Given n ≥ 2, and n integers $0 = k_1 < k_2 < ... < k_n$, and for every prime p ≤ n the set of remainders $k_i mod p$ has fewer than p elements, then there are infinitely many integers p such that $p + k_i$ is prime for every 1 ≤ i ≤ n.



                If there are n primes from 2 to 2+m-1, and we find $k_1$ to $k_{n+1}$ with $k_{n+1} ≤ m-1$, then the hypothesis is that there are infinitely many sequences of m consecutive integers containing n+1 primes.



                Finding such a sequence was quite hard but was done. I think there are sequences known that point to 5 more primes in m consecutive integers than in 2 to m-1, but beyond that it's limited by processing power (or by willingness to use that processing power).







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                answered Aug 17 at 23:30


























                community wiki





                gnasher729












                • 1




                  $begingroup$
                  The 1st paragraph is called the Hardy-Littlewood 2nd conjecture, the 3rd paragraph id called the Hardy-Littlewood 1st conjecture, see the answer from user21820.
                  $endgroup$
                  – Gerry Myerson
                  2 days ago














                • 1




                  $begingroup$
                  The 1st paragraph is called the Hardy-Littlewood 2nd conjecture, the 3rd paragraph id called the Hardy-Littlewood 1st conjecture, see the answer from user21820.
                  $endgroup$
                  – Gerry Myerson
                  2 days ago








                1




                1




                $begingroup$
                The 1st paragraph is called the Hardy-Littlewood 2nd conjecture, the 3rd paragraph id called the Hardy-Littlewood 1st conjecture, see the answer from user21820.
                $endgroup$
                – Gerry Myerson
                2 days ago




                $begingroup$
                The 1st paragraph is called the Hardy-Littlewood 2nd conjecture, the 3rd paragraph id called the Hardy-Littlewood 1st conjecture, see the answer from user21820.
                $endgroup$
                – Gerry Myerson
                2 days ago











                3











                $begingroup$

                The number of distinct magic squares, for deceptively small sizes



                A magic square of order $n$ is a square grid of $n times n$ boxes where each box contains one distinct integer from the interval $[1 .. n^2]$, so that the sums of the numbers on each row, on each column and on each of the two diagonals are equal to each other. They have been studied for millenia by mathematicians in China, India and Persia, and continue to be of interest to both hobbyist and professional mathematicians.



                The smallest magic squares, excluding the trivial case where $n = 1$, are of order $3$. This is one of them:



                begin{array}{|c|c|c|}
                hline
                8 & 3 & 4 \ hline
                1 & 5 & 9 \ hline
                6 & 7 & 2 \ hline
                end{array}



                In a sense, this is the only solution to the problem of this size: the other 7 magic squares of order 3 are mirrored and/or rotated versions of this grid.



                We know the number of magic squares of orders 3, 4 and 5. The number of magic squares of order 6 is not known, but is believed to be in the order of $10^{19}$. The number of magic squares is not known for any order greater than 6 either. It should be noted that constructing magic squares of odd and doubly-even (divisible by four) orders is generally regarded as a simpler feat than constructing magic squares of singly-even orders like 6, although this may not guarantee the ease of enumerating all magic squares of such order over enumerating those of orders of smaller singly even numbers.



                This problem is trivially solvable if the computational power constraint wouldn't stop us: we could just enumerate all $36!$ possible ways to fit the numbers in the grid, and check each for magic number property. In practice, we can apply a fair bit of pruning to explore only a small fraction of this space. We know the sum that should appear on each row/column/diagonal and we know that only an eighth of the configurations need to be checked to account for their mirrored and/or rotated copies; these and further insights or heuristics may be enough to make the problem computationally tractable for a well-supplied research effort in the coming years.



                However, this is in a sense cop-out; even if we solve the number of magic squares of order 6, we'll still be left wondering what the number of magic squares of order 7 and greater might be --- that is, unless someone figures out a more efficient way to compute it than raw enumeration.






                share|cite|improve this answer











                $endgroup$















                • $begingroup$
                  Reading this Parker's Square comes to my mind if you know what I mean
                  $endgroup$
                  – StackUpPhysics
                  2 days ago










                • $begingroup$
                  The reference if you didn't get it- bradyharanblog.com/the-parker-square
                  $endgroup$
                  – StackUpPhysics
                  2 days ago
















                3











                $begingroup$

                The number of distinct magic squares, for deceptively small sizes



                A magic square of order $n$ is a square grid of $n times n$ boxes where each box contains one distinct integer from the interval $[1 .. n^2]$, so that the sums of the numbers on each row, on each column and on each of the two diagonals are equal to each other. They have been studied for millenia by mathematicians in China, India and Persia, and continue to be of interest to both hobbyist and professional mathematicians.



                The smallest magic squares, excluding the trivial case where $n = 1$, are of order $3$. This is one of them:



                begin{array}{|c|c|c|}
                hline
                8 & 3 & 4 \ hline
                1 & 5 & 9 \ hline
                6 & 7 & 2 \ hline
                end{array}



                In a sense, this is the only solution to the problem of this size: the other 7 magic squares of order 3 are mirrored and/or rotated versions of this grid.



                We know the number of magic squares of orders 3, 4 and 5. The number of magic squares of order 6 is not known, but is believed to be in the order of $10^{19}$. The number of magic squares is not known for any order greater than 6 either. It should be noted that constructing magic squares of odd and doubly-even (divisible by four) orders is generally regarded as a simpler feat than constructing magic squares of singly-even orders like 6, although this may not guarantee the ease of enumerating all magic squares of such order over enumerating those of orders of smaller singly even numbers.



                This problem is trivially solvable if the computational power constraint wouldn't stop us: we could just enumerate all $36!$ possible ways to fit the numbers in the grid, and check each for magic number property. In practice, we can apply a fair bit of pruning to explore only a small fraction of this space. We know the sum that should appear on each row/column/diagonal and we know that only an eighth of the configurations need to be checked to account for their mirrored and/or rotated copies; these and further insights or heuristics may be enough to make the problem computationally tractable for a well-supplied research effort in the coming years.



                However, this is in a sense cop-out; even if we solve the number of magic squares of order 6, we'll still be left wondering what the number of magic squares of order 7 and greater might be --- that is, unless someone figures out a more efficient way to compute it than raw enumeration.






                share|cite|improve this answer











                $endgroup$















                • $begingroup$
                  Reading this Parker's Square comes to my mind if you know what I mean
                  $endgroup$
                  – StackUpPhysics
                  2 days ago










                • $begingroup$
                  The reference if you didn't get it- bradyharanblog.com/the-parker-square
                  $endgroup$
                  – StackUpPhysics
                  2 days ago














                3












                3








                3





                $begingroup$

                The number of distinct magic squares, for deceptively small sizes



                A magic square of order $n$ is a square grid of $n times n$ boxes where each box contains one distinct integer from the interval $[1 .. n^2]$, so that the sums of the numbers on each row, on each column and on each of the two diagonals are equal to each other. They have been studied for millenia by mathematicians in China, India and Persia, and continue to be of interest to both hobbyist and professional mathematicians.



                The smallest magic squares, excluding the trivial case where $n = 1$, are of order $3$. This is one of them:



                begin{array}{|c|c|c|}
                hline
                8 & 3 & 4 \ hline
                1 & 5 & 9 \ hline
                6 & 7 & 2 \ hline
                end{array}



                In a sense, this is the only solution to the problem of this size: the other 7 magic squares of order 3 are mirrored and/or rotated versions of this grid.



                We know the number of magic squares of orders 3, 4 and 5. The number of magic squares of order 6 is not known, but is believed to be in the order of $10^{19}$. The number of magic squares is not known for any order greater than 6 either. It should be noted that constructing magic squares of odd and doubly-even (divisible by four) orders is generally regarded as a simpler feat than constructing magic squares of singly-even orders like 6, although this may not guarantee the ease of enumerating all magic squares of such order over enumerating those of orders of smaller singly even numbers.



                This problem is trivially solvable if the computational power constraint wouldn't stop us: we could just enumerate all $36!$ possible ways to fit the numbers in the grid, and check each for magic number property. In practice, we can apply a fair bit of pruning to explore only a small fraction of this space. We know the sum that should appear on each row/column/diagonal and we know that only an eighth of the configurations need to be checked to account for their mirrored and/or rotated copies; these and further insights or heuristics may be enough to make the problem computationally tractable for a well-supplied research effort in the coming years.



                However, this is in a sense cop-out; even if we solve the number of magic squares of order 6, we'll still be left wondering what the number of magic squares of order 7 and greater might be --- that is, unless someone figures out a more efficient way to compute it than raw enumeration.






                share|cite|improve this answer











                $endgroup$



                The number of distinct magic squares, for deceptively small sizes



                A magic square of order $n$ is a square grid of $n times n$ boxes where each box contains one distinct integer from the interval $[1 .. n^2]$, so that the sums of the numbers on each row, on each column and on each of the two diagonals are equal to each other. They have been studied for millenia by mathematicians in China, India and Persia, and continue to be of interest to both hobbyist and professional mathematicians.



                The smallest magic squares, excluding the trivial case where $n = 1$, are of order $3$. This is one of them:



                begin{array}{|c|c|c|}
                hline
                8 & 3 & 4 \ hline
                1 & 5 & 9 \ hline
                6 & 7 & 2 \ hline
                end{array}



                In a sense, this is the only solution to the problem of this size: the other 7 magic squares of order 3 are mirrored and/or rotated versions of this grid.



                We know the number of magic squares of orders 3, 4 and 5. The number of magic squares of order 6 is not known, but is believed to be in the order of $10^{19}$. The number of magic squares is not known for any order greater than 6 either. It should be noted that constructing magic squares of odd and doubly-even (divisible by four) orders is generally regarded as a simpler feat than constructing magic squares of singly-even orders like 6, although this may not guarantee the ease of enumerating all magic squares of such order over enumerating those of orders of smaller singly even numbers.



                This problem is trivially solvable if the computational power constraint wouldn't stop us: we could just enumerate all $36!$ possible ways to fit the numbers in the grid, and check each for magic number property. In practice, we can apply a fair bit of pruning to explore only a small fraction of this space. We know the sum that should appear on each row/column/diagonal and we know that only an eighth of the configurations need to be checked to account for their mirrored and/or rotated copies; these and further insights or heuristics may be enough to make the problem computationally tractable for a well-supplied research effort in the coming years.



                However, this is in a sense cop-out; even if we solve the number of magic squares of order 6, we'll still be left wondering what the number of magic squares of order 7 and greater might be --- that is, unless someone figures out a more efficient way to compute it than raw enumeration.







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                answered 2 days ago


























                community wiki





                kviiri
















                • $begingroup$
                  Reading this Parker's Square comes to my mind if you know what I mean
                  $endgroup$
                  – StackUpPhysics
                  2 days ago










                • $begingroup$
                  The reference if you didn't get it- bradyharanblog.com/the-parker-square
                  $endgroup$
                  – StackUpPhysics
                  2 days ago


















                • $begingroup$
                  Reading this Parker's Square comes to my mind if you know what I mean
                  $endgroup$
                  – StackUpPhysics
                  2 days ago










                • $begingroup$
                  The reference if you didn't get it- bradyharanblog.com/the-parker-square
                  $endgroup$
                  – StackUpPhysics
                  2 days ago
















                $begingroup$
                Reading this Parker's Square comes to my mind if you know what I mean
                $endgroup$
                – StackUpPhysics
                2 days ago




                $begingroup$
                Reading this Parker's Square comes to my mind if you know what I mean
                $endgroup$
                – StackUpPhysics
                2 days ago












                $begingroup$
                The reference if you didn't get it- bradyharanblog.com/the-parker-square
                $endgroup$
                – StackUpPhysics
                2 days ago




                $begingroup$
                The reference if you didn't get it- bradyharanblog.com/the-parker-square
                $endgroup$
                – StackUpPhysics
                2 days ago











                0











                $begingroup$

                I believe a problem connected with Graham's number is one of the things you are looking for. It is an upper bound to problem in Ramsey theory, that looks for a number $N$ satisfying certain criteria. I do not know much about that, but you can read more here https://en.wikipedia.org/wiki/Graham%27s_number .



                But from my understanding, there are bounds on the number $N$, however the range of possible values derived from those bounds is still enormously large, way beyond computational possibilities of today (and probably ever). But with arbitrarily large, yet still finite computational power, the problem could be solved.






                share|cite|improve this answer











                $endgroup$




















                  0











                  $begingroup$

                  I believe a problem connected with Graham's number is one of the things you are looking for. It is an upper bound to problem in Ramsey theory, that looks for a number $N$ satisfying certain criteria. I do not know much about that, but you can read more here https://en.wikipedia.org/wiki/Graham%27s_number .



                  But from my understanding, there are bounds on the number $N$, however the range of possible values derived from those bounds is still enormously large, way beyond computational possibilities of today (and probably ever). But with arbitrarily large, yet still finite computational power, the problem could be solved.






                  share|cite|improve this answer











                  $endgroup$


















                    0












                    0








                    0





                    $begingroup$

                    I believe a problem connected with Graham's number is one of the things you are looking for. It is an upper bound to problem in Ramsey theory, that looks for a number $N$ satisfying certain criteria. I do not know much about that, but you can read more here https://en.wikipedia.org/wiki/Graham%27s_number .



                    But from my understanding, there are bounds on the number $N$, however the range of possible values derived from those bounds is still enormously large, way beyond computational possibilities of today (and probably ever). But with arbitrarily large, yet still finite computational power, the problem could be solved.






                    share|cite|improve this answer











                    $endgroup$



                    I believe a problem connected with Graham's number is one of the things you are looking for. It is an upper bound to problem in Ramsey theory, that looks for a number $N$ satisfying certain criteria. I do not know much about that, but you can read more here https://en.wikipedia.org/wiki/Graham%27s_number .



                    But from my understanding, there are bounds on the number $N$, however the range of possible values derived from those bounds is still enormously large, way beyond computational possibilities of today (and probably ever). But with arbitrarily large, yet still finite computational power, the problem could be solved.







                    share|cite|improve this answer














                    share|cite|improve this answer



                    share|cite|improve this answer








                    edited 2 days ago


























                    community wiki





                    3 revs, 2 users 89%
                    TStancek



























                        0











                        $begingroup$

                        What are the odds in Klondike Solitare? An attempt was made based on perfect knowledge yielding 79%, but the player doesn't have perfect knowledge. There's a bunch of Monte-Carlo results on that site; but a direct attack is far beyond reach, and it's not even known if the strategy they're using is actually optimal.



                        "One of the embarrassments of applied mathematics that we cannot determine the odds of winning the common game of solitaire."






                        share|cite|improve this answer











                        $endgroup$




















                          0











                          $begingroup$

                          What are the odds in Klondike Solitare? An attempt was made based on perfect knowledge yielding 79%, but the player doesn't have perfect knowledge. There's a bunch of Monte-Carlo results on that site; but a direct attack is far beyond reach, and it's not even known if the strategy they're using is actually optimal.



                          "One of the embarrassments of applied mathematics that we cannot determine the odds of winning the common game of solitaire."






                          share|cite|improve this answer











                          $endgroup$


















                            0












                            0








                            0





                            $begingroup$

                            What are the odds in Klondike Solitare? An attempt was made based on perfect knowledge yielding 79%, but the player doesn't have perfect knowledge. There's a bunch of Monte-Carlo results on that site; but a direct attack is far beyond reach, and it's not even known if the strategy they're using is actually optimal.



                            "One of the embarrassments of applied mathematics that we cannot determine the odds of winning the common game of solitaire."






                            share|cite|improve this answer











                            $endgroup$



                            What are the odds in Klondike Solitare? An attempt was made based on perfect knowledge yielding 79%, but the player doesn't have perfect knowledge. There's a bunch of Monte-Carlo results on that site; but a direct attack is far beyond reach, and it's not even known if the strategy they're using is actually optimal.



                            "One of the embarrassments of applied mathematics that we cannot determine the odds of winning the common game of solitaire."







                            share|cite|improve this answer














                            share|cite|improve this answer



                            share|cite|improve this answer








                            answered yesterday


























                            community wiki





                            Joshua



























                                -2











                                $begingroup$

                                Prime gaps - https://en.wikipedia.org/wiki/Prime_gap - of maximum known merit are found by increasing CPU (and GPU) computational power on the gapcoin network. See: https://gapcoin.club




                                ... So the difficulty will simply be the length of the prime gap?



                                Not exactly. The average length of a prime gap with the starting prime
                                p, is log(p), which means that the average prime gap size increases
                                with lager primes. Then, instead of the pure length, we use the merit
                                of the prime gap, which is the ratio of the gap's size to the average
                                gap size.



                                Let p be the prime starting a prime gap, then m = gapsize/log(p) will
                                be the merit of this prime gap.



                                Also a pseudo random number is calculated from p to provide finer
                                difficulty adjustment.



                                Let rand(p) be a pseudo random function with 0 less than rand(p) less
                                than 1. Then, for a prime gap starting at prime p with size s, the
                                difficulty will be s/log(p) + 2/log(p) * rand(p), where 2/log(p) is
                                the average distance between a gap of size s and s + 2 (the next
                                greater gap) in the proximity of p.



                                When it actually comes to mining, there are two additional fields
                                added to the Blockheader, named “shift” and “adder”. We will calculate
                                the prime p as sha256(Blockheader) * 2^shift + adder. As an additional
                                criterion the adder has to be smaller than 2^shift to avoid that the
                                PoW could be reused. ...




                                Source: gapcoin.org



                                ...



                                https://web.stanford.edu/~tonyfeng/bounded_gaps.pdf




                                ... (Twin prime conjecture) ...



                                ... This is a just a special case of a far-reaching conjecture
                                of Hardy and Lit- tlewood describing the frequency of prime
                                gaps of any sizes. The Hardy- Littlewood conjecture predicts not
                                only how often twin primes occur, but also how often any finite
                                tuple
                                of the form ( n
                                + h 1 , n
                                + h 2 , . . . , n
                                + h k ) consists en- tirely of prime numbers. But even though analytic number theorists have be- lieved for many years that they know the
                                answers to these questions, progress towards proving the existence of
                                small gaps between primes has been slow. As recently as 2005 , the
                                problem of establishing infinitely many bounded gaps be- tween primes
                                was considered by many mathematicians to be “hopeless” ...




                                ...



                                Further,



                                List of unsolved problems in mathematics:
                                https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics






                                share|cite|improve this answer











                                $endgroup$















                                • $begingroup$
                                  The OP wants a problem that is known to be solvable with a finite algorithm, which afaik is not known to exist for finding either the primegap of maximum merit nor the twin prime conjecture.
                                  $endgroup$
                                  – Jam
                                  2 days ago
















                                -2











                                $begingroup$

                                Prime gaps - https://en.wikipedia.org/wiki/Prime_gap - of maximum known merit are found by increasing CPU (and GPU) computational power on the gapcoin network. See: https://gapcoin.club




                                ... So the difficulty will simply be the length of the prime gap?



                                Not exactly. The average length of a prime gap with the starting prime
                                p, is log(p), which means that the average prime gap size increases
                                with lager primes. Then, instead of the pure length, we use the merit
                                of the prime gap, which is the ratio of the gap's size to the average
                                gap size.



                                Let p be the prime starting a prime gap, then m = gapsize/log(p) will
                                be the merit of this prime gap.



                                Also a pseudo random number is calculated from p to provide finer
                                difficulty adjustment.



                                Let rand(p) be a pseudo random function with 0 less than rand(p) less
                                than 1. Then, for a prime gap starting at prime p with size s, the
                                difficulty will be s/log(p) + 2/log(p) * rand(p), where 2/log(p) is
                                the average distance between a gap of size s and s + 2 (the next
                                greater gap) in the proximity of p.



                                When it actually comes to mining, there are two additional fields
                                added to the Blockheader, named “shift” and “adder”. We will calculate
                                the prime p as sha256(Blockheader) * 2^shift + adder. As an additional
                                criterion the adder has to be smaller than 2^shift to avoid that the
                                PoW could be reused. ...




                                Source: gapcoin.org



                                ...



                                https://web.stanford.edu/~tonyfeng/bounded_gaps.pdf




                                ... (Twin prime conjecture) ...



                                ... This is a just a special case of a far-reaching conjecture
                                of Hardy and Lit- tlewood describing the frequency of prime
                                gaps of any sizes. The Hardy- Littlewood conjecture predicts not
                                only how often twin primes occur, but also how often any finite
                                tuple
                                of the form ( n
                                + h 1 , n
                                + h 2 , . . . , n
                                + h k ) consists en- tirely of prime numbers. But even though analytic number theorists have be- lieved for many years that they know the
                                answers to these questions, progress towards proving the existence of
                                small gaps between primes has been slow. As recently as 2005 , the
                                problem of establishing infinitely many bounded gaps be- tween primes
                                was considered by many mathematicians to be “hopeless” ...




                                ...



                                Further,



                                List of unsolved problems in mathematics:
                                https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics






                                share|cite|improve this answer











                                $endgroup$















                                • $begingroup$
                                  The OP wants a problem that is known to be solvable with a finite algorithm, which afaik is not known to exist for finding either the primegap of maximum merit nor the twin prime conjecture.
                                  $endgroup$
                                  – Jam
                                  2 days ago














                                -2












                                -2








                                -2





                                $begingroup$

                                Prime gaps - https://en.wikipedia.org/wiki/Prime_gap - of maximum known merit are found by increasing CPU (and GPU) computational power on the gapcoin network. See: https://gapcoin.club




                                ... So the difficulty will simply be the length of the prime gap?



                                Not exactly. The average length of a prime gap with the starting prime
                                p, is log(p), which means that the average prime gap size increases
                                with lager primes. Then, instead of the pure length, we use the merit
                                of the prime gap, which is the ratio of the gap's size to the average
                                gap size.



                                Let p be the prime starting a prime gap, then m = gapsize/log(p) will
                                be the merit of this prime gap.



                                Also a pseudo random number is calculated from p to provide finer
                                difficulty adjustment.



                                Let rand(p) be a pseudo random function with 0 less than rand(p) less
                                than 1. Then, for a prime gap starting at prime p with size s, the
                                difficulty will be s/log(p) + 2/log(p) * rand(p), where 2/log(p) is
                                the average distance between a gap of size s and s + 2 (the next
                                greater gap) in the proximity of p.



                                When it actually comes to mining, there are two additional fields
                                added to the Blockheader, named “shift” and “adder”. We will calculate
                                the prime p as sha256(Blockheader) * 2^shift + adder. As an additional
                                criterion the adder has to be smaller than 2^shift to avoid that the
                                PoW could be reused. ...




                                Source: gapcoin.org



                                ...



                                https://web.stanford.edu/~tonyfeng/bounded_gaps.pdf




                                ... (Twin prime conjecture) ...



                                ... This is a just a special case of a far-reaching conjecture
                                of Hardy and Lit- tlewood describing the frequency of prime
                                gaps of any sizes. The Hardy- Littlewood conjecture predicts not
                                only how often twin primes occur, but also how often any finite
                                tuple
                                of the form ( n
                                + h 1 , n
                                + h 2 , . . . , n
                                + h k ) consists en- tirely of prime numbers. But even though analytic number theorists have be- lieved for many years that they know the
                                answers to these questions, progress towards proving the existence of
                                small gaps between primes has been slow. As recently as 2005 , the
                                problem of establishing infinitely many bounded gaps be- tween primes
                                was considered by many mathematicians to be “hopeless” ...




                                ...



                                Further,



                                List of unsolved problems in mathematics:
                                https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics






                                share|cite|improve this answer











                                $endgroup$



                                Prime gaps - https://en.wikipedia.org/wiki/Prime_gap - of maximum known merit are found by increasing CPU (and GPU) computational power on the gapcoin network. See: https://gapcoin.club




                                ... So the difficulty will simply be the length of the prime gap?



                                Not exactly. The average length of a prime gap with the starting prime
                                p, is log(p), which means that the average prime gap size increases
                                with lager primes. Then, instead of the pure length, we use the merit
                                of the prime gap, which is the ratio of the gap's size to the average
                                gap size.



                                Let p be the prime starting a prime gap, then m = gapsize/log(p) will
                                be the merit of this prime gap.



                                Also a pseudo random number is calculated from p to provide finer
                                difficulty adjustment.



                                Let rand(p) be a pseudo random function with 0 less than rand(p) less
                                than 1. Then, for a prime gap starting at prime p with size s, the
                                difficulty will be s/log(p) + 2/log(p) * rand(p), where 2/log(p) is
                                the average distance between a gap of size s and s + 2 (the next
                                greater gap) in the proximity of p.



                                When it actually comes to mining, there are two additional fields
                                added to the Blockheader, named “shift” and “adder”. We will calculate
                                the prime p as sha256(Blockheader) * 2^shift + adder. As an additional
                                criterion the adder has to be smaller than 2^shift to avoid that the
                                PoW could be reused. ...




                                Source: gapcoin.org



                                ...



                                https://web.stanford.edu/~tonyfeng/bounded_gaps.pdf




                                ... (Twin prime conjecture) ...



                                ... This is a just a special case of a far-reaching conjecture
                                of Hardy and Lit- tlewood describing the frequency of prime
                                gaps of any sizes. The Hardy- Littlewood conjecture predicts not
                                only how often twin primes occur, but also how often any finite
                                tuple
                                of the form ( n
                                + h 1 , n
                                + h 2 , . . . , n
                                + h k ) consists en- tirely of prime numbers. But even though analytic number theorists have be- lieved for many years that they know the
                                answers to these questions, progress towards proving the existence of
                                small gaps between primes has been slow. As recently as 2005 , the
                                problem of establishing infinitely many bounded gaps be- tween primes
                                was considered by many mathematicians to be “hopeless” ...




                                ...



                                Further,



                                List of unsolved problems in mathematics:
                                https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics







                                share|cite|improve this answer














                                share|cite|improve this answer



                                share|cite|improve this answer








                                answered Aug 18 at 21:36


























                                community wiki





                                Gapcoin Club
















                                • $begingroup$
                                  The OP wants a problem that is known to be solvable with a finite algorithm, which afaik is not known to exist for finding either the primegap of maximum merit nor the twin prime conjecture.
                                  $endgroup$
                                  – Jam
                                  2 days ago


















                                • $begingroup$
                                  The OP wants a problem that is known to be solvable with a finite algorithm, which afaik is not known to exist for finding either the primegap of maximum merit nor the twin prime conjecture.
                                  $endgroup$
                                  – Jam
                                  2 days ago
















                                $begingroup$
                                The OP wants a problem that is known to be solvable with a finite algorithm, which afaik is not known to exist for finding either the primegap of maximum merit nor the twin prime conjecture.
                                $endgroup$
                                – Jam
                                2 days ago




                                $begingroup$
                                The OP wants a problem that is known to be solvable with a finite algorithm, which afaik is not known to exist for finding either the primegap of maximum merit nor the twin prime conjecture.
                                $endgroup$
                                – Jam
                                2 days ago


















                                draft saved

                                draft discarded




















































                                Thanks for contributing an answer to Mathematics Stack Exchange!


                                • Please be sure to answer the question. Provide details and share your research!

                                But avoid



                                • Asking for help, clarification, or responding to other answers.

                                • Making statements based on opinion; back them up with references or personal experience.


                                Use MathJax to format equations. MathJax reference.


                                To learn more, see our tips on writing great answers.




                                draft saved


                                draft discarded














                                StackExchange.ready(
                                function () {
                                StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3325462%2funsolved-problems-not-independent-of-zfc-due-to-lack-of-computational-power%23new-answer', 'question_page');
                                }
                                );

                                Post as a guest















                                Required, but never shown





















































                                Required, but never shown














                                Required, but never shown












                                Required, but never shown







                                Required, but never shown

































                                Required, but never shown














                                Required, but never shown












                                Required, but never shown







                                Required, but never shown







                                Popular posts from this blog

                                Taj Mahal Inhaltsverzeichnis Aufbau | Geschichte | 350-Jahr-Feier | Heutige Bedeutung | Siehe auch |...

                                Baia Sprie Cuprins Etimologie | Istorie | Demografie | Politică și administrație | Arii naturale...

                                Nicolae Petrescu-Găină Cuprins Biografie | Opera | In memoriam | Varia | Controverse, incertitudini...