Wikipedia:Reference desk/Archives/Mathematics/2024 February 16

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 16

What is the largest even number that cannot be written as sum of two composite numbers coprime to 6?

What is the largest even number that cannot be written as sum of two composite numbers coprime to 6? 2402:7500:92D:3AAC:1D78:709A:792E:546C (talk) 08:10, 16 February 2024 (UTC)

A quick Python script that I gave some time to run suggests that the last such number is probably 166. Given that the existence of a larger even number k with this property implies that half of the numbers below k congruent to 1 mod 6, 5 mod 6, or either, are prime (note: that's pretty much at least 1/12th of all numbers up to k), it seems extraordinarily unlikely that such k exists. GalacticShoe (talk) 09:10, 16 February 2024 (UTC)

Another note: an effective form of the prime number theorem could probably establish an upper bound above which it is literally impossible for that many numbers to be prime. GalacticShoe (talk) 09:21, 16 February 2024 (UTC)

If $n=6k$ cannot be written as the sum of two composite numbers coprime to $6$, this implies that in each of the $k$ pairs $(1,6k-1),(7,6k-7),\ldots ,(6k-5,5)$ there is at least one prime. In other words, there are at least $k$ primes less than $n$, and thus $\pi (n)\geq {\frac {n}{6}}$.

Meanwhile, if $n=6k+2$ has this property, then in each of the pairs $(1,6k+1),(7,6k-5),\ldots ,(6k+1,1)$ there is at least one prime. This time, because of double counting, there are $\lceil {\frac {k+1}{2}}\rceil$ primes, and so $\pi (n)\geq \lceil {\frac {n+4}{12}}\rceil$.

Similarly, if $n=6k+4$ has this property, then in each of the pairs $(5,6k-1),(11,6k-7),\ldots ,(6k-1,5)$ there is at least one prime. Again, because of double counting, there are $\lceil {\frac {k}{2}}\rceil$ primes, and so $\pi (n)\geq \lceil {\frac {n-4}{12}}\rceil$.

When $n>52$, all of these bounds are greater than ${\frac {n}{13}}$, so in general the existence of such $n>52$ implies that $\pi (n)\geq {\frac {n}{13}}$, or ${\frac {\pi (n)}{n}}>{\frac {1}{13}}$.

Now, using Dusart's result listed in Prime number theorem#Non-asymptotic bounds on the prime-counting function, ${\frac {\pi (x)}{x}}<{\frac {1}{\log(x)-1.1}}$ for $x\geq 60184$, while ${\frac {1}{\log(x)-1.1}}<{\frac {1}{13}}$ for $x>e^{14.1}\approx 1329083$, so ${\frac {\pi (x)}{x}}<{\frac {1}{13}}$ for $x>e^{14.1}$. This means that no $n$ with the desired property exists above $e^{14.1}$, lest we run into a contradiction. It's pretty easy from there to check that indeed within the range up to $1329083$, the last of the even numbers with this property is $166$. GalacticShoe (talk) 18:43, 16 February 2024 (UTC)

Why the halting problem cannot be solved by avoid self-reference?

The proof of the halting problem cannot be solved uses the self-reference, i.e. "def g(): if halts(g): loop_forever()", however, some software can avoid self-reference automatically, e.g. if we enter a self-reference in Microsoft Excel, e.g. if we enter "=A1+1" in the lattice A1 in Microsoft Excel, then it will return "Error: Self-reference!" Thus, we may make a Turing machine, if we enter a self-reference, include "def g(): if halts(g): loop_forever()", then it will return "Error: Self-reference!", thus, the halting problem may be solved using such a Turing machine. 2402:7500:92D:3AAC:65D6:1566:C11B:2095 (talk) 10:02, 16 February 2024 (UTC)

Turing's proof, which introduced the concept of what we now call "Turing machine", did not use direct, explicit self-reference. Turing's approach was very similar to Gödel's proof of his first incompleteness theorem; both use the method of the so-called "diagonal lemma" to create self-reference indirectly. This is essentially the same trick as used to make self-reproducing programs. One cannot rule out such indirect self-referencing; deciding whether it is present is itself also undecidable.  --Lambiam 11:43, 16 February 2024 (UTC)

So ... how exactly would you calculate the factorial of a value in Excel just using the normal arithmetic operations? NadVolum (talk) 11:51, 16 February 2024 (UTC)

While this is not possible in a formula, one can write a loop in VBA to compute the factorial of a given value while not using any form of self-reference.  --Lambiam 12:44, 16 February 2024 (UTC)

You just need one while loop and some if statements and you've got a Turing machine. NadVolum (talk) 13:50, 16 February 2024 (UTC)

Note that the OP's claim was that the halting problem could be solved by, of all things, a (self-reference detecting) Turing machine. The observation that Excel+VBA is Turing complete has little dissuasive power regarding that claim.  --Lambiam 15:16, 16 February 2024 (UTC)

I was assuming they meant Excel without using VBA. NadVolum (talk) 19:24, 16 February 2024 (UTC)

I'm getting lost. As I interpret it, the OP's basic argument goes like this:

• Premise 1: The halting problem is undecidable because of self-reference.
• Premise 2: Excel can detect self-reference.
• Conclusion 1 (from Premise 2): Therefore we can make a Turing machine that detects self-reference.
• Conclusion 2 (from Premise 1 and Conclusion 1): This Turing machine can solve the halting problem.

As I aimed to point out, the premises are flawed. (Even if they were correct, the conclusions do not follow from the premises, but this is now moot.)

I fail to see the relevance in this context of questioning the capability of Excel to compute the factorial function, with or without VBA.  --Lambiam 21:01, 16 February 2024 (UTC)

I was pointing out that his 'Thus, we may make a Turing machine,' was wrong. The business about detecting self referencs only really makes much sense if we don't use VBA or confine ourselves to simple functions in VBA and you can't make a Turing machine out of that. If you use anything slightly more complex then not only can you not detect self references between cells but you could also implement a Turing machine inside one witout bothering about references between cells. It certainly looked to me like he was assumng not using VBA in which case I can't see how to do a factorial never mind a Turing machine. NadVolum (talk) 22:39, 16 February 2024 (UTC)

I see. I had a different construction for the missing link in the "Thus, we may" jump:

• Premise: Excel can detect self-reference.
• Missing link: We can make a Turing machine do anything Excel can do.
• Conclusion: Therefore we can make a Turing machine that detects self-reference.

In this construction Turing completeness for Excel is not required.  --Lambiam 09:22, 17 February 2024 (UTC)

I think the root problem here is that the phrase "self-reference" means something different in a spreadsheet than in mathematical logic. In a spreadsheet it's a purely graph-theoretical concept. Form a directed graph where cell (node) is joined to another if the first cell uses the value of the other cell in a formula. If the resulting graph has a cycle then you say there is "self-reference". That has nothing to do with self-reference in it's logical sense; you can type "This sentence is false." into as many cells as you want and no self-reference will be detected. An algorithm that detects self-reference in a Turing machine would have a lot more to do. It would have to decode the encoding of the machine to determine what function it's meant to compute, and somehow determine that that function is run the machine on itself. That seems like a lot bigger ask than to find cycles in a graph. --RDBury (talk) 11:03, 17 February 2024 (UTC)

Selfreference isn't really needed anyway. def ApplySelf(x): Apply(x,x); is no more a self reference than def Twice(x): x+x; And Apply can be a simple loop doing one step at a time with no self reference. They might be interested in Goodstein's theorem which demonstrates that even straightforward axioms for arithmetic can be insufficient for straightforward theorems. NadVolum (talk) 13:35, 17 February 2024 (UTC)