Wikipedia:Reference desk/Archives/Mathematics/2023 September 15

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.

September 15

Probability that all sums are odd

I am not too confident about probability calculations, so hope that someone can confirm that what follows is correct. The problem is to assign the values 1 to 9 randomly to a three by three table and determine the probability that all row sums and all column sums are odd. The sum of three integers is odd only if all three are, or exactly one is. It follows that the odd values 1, 3, 5, 7 and 9 must all be in one row and one column, of which there are nine possible pairings. For any particular such pair, the odd integers can be assigned to the five places in 5! ways and the even ones to the remaining four places in 4! ways. The total number of ways of getting all six sums odd is then 9 x 5! x 4!. The nine integers can be assigned to the table in 9! ways, so the required probability is (9 x 5! x 4!)/9!, reducing to 1/14. 2A00:23C6:AA0D:F501:9CC5:B6D3:8978:7E84 (talk) 12:59, 15 September 2023 (UTC)

Looks good to me. GalacticShoe (talk) 14:30, 15 September 2023 (UTC)

Thanks, I couldn't see a flaw so hoped it was OK.2A00:23C6:AA0D:F501:DC56:B4BF:83E:92E4 (talk) 15:26, 15 September 2023 (UTC)

I wrote a quick program to test all 362,880 permutations of the nine digits, and found that 25,920 of them result in odd row and column sums. This is exactly 1/14 of the total, confirming your calculation. CodeTalker (talk) 19:12, 15 September 2023 (UTC)

The probabilities for an n×n table, for n = 0, 1, 2, 3, go like 1/1, 1/1, 1/3, 1/14. I thought that this might in general be the reciprocal of a whole number, but for n = 4 I find 8/715 = 1/89.375.  --Lambiam 21:23, 15 September 2023 (UTC)

Since, in general, the probabilities for an $n\times n$ table are ${\frac {A(n)(\lfloor {\frac {n^{2}}{2}}\rfloor )!(\lceil {\frac {n^{2}}{2}}\rceil )!}{(n^{2})!}}=A(n)/{n^{2} \choose {\lfloor {\frac {n^{2}}{2}}\rfloor }}$ where $A(n)$ is the number of arrangements of $\lceil {\frac {n^{2}}{2}}\rceil$ odd and $\lfloor {\frac {n^{2}}{2}}\rfloor$ even numbers in the square that yields all odd-sum rows and columns, I think the sequence of $A(n)$ is of particular interest. Starting with $n=1$, the sequence goes $1,2,9,144,20700,8930240,\ldots$ GalacticShoe (talk) 01:13, 16 September 2023 (UTC)

If you consider arrangements of $\lceil {\frac {n^{2}}{2}}\rceil$ odd and $\lfloor {\frac {n^{2}}{2}}\rfloor$ even numbers in the square that yields all odd-sum rows and columns to be invariant under rotation and reflection, then the number of unique arrangements under invariance, starting with $n=1$, is $1,1,3,24,2684,1118260,\ldots$ GalacticShoe (talk) 18:27, 18 September 2023 (UTC)

Can these numbers be perfect powers?

1. Can product of n (n>1) consecutive positive integers be perfect powers? If so, are there infinitely many such numbers?

2. Can product of n (n>1) consecutive positive integers divided by n! be perfect powers? (Other than that there are infinitely many cases that the product of 2 consecutive positive integers divided by 2! = 2 are squares (see OEIS: A001110), i.e. at least one of n and the exponent of the perfect power must be > 2) If so, are there infinitely many such numbers?

—— 36.234.121.52 (talk) 23:06, 15 September 2023 (UTC)

1. No, a fact that Erdős and Selfridge proved in 1975. GalacticShoe (talk) 04:51, 16 September 2023 (UTC)

2. In the current way this is phrased, you can easily construct these numbers based on the fact that all $n^{2}$ are products of $2$ through $n^{2}$ divided by $(n^{2}-1)!$. If you want to ask instead what binomial coefficients ${n \choose k}$ are perfect $m$-th powers, Erdős has a famous proof that there are none if $4\leq k\leq n-4$, and Gyory proved in 1997 that $k=2\Rightarrow m=2$ (and there are infinitely many cases of this, as you mentioned) while the only case for $k=3$ is ${50 \choose 3}=140^{2}$. GalacticShoe (talk) 04:40, 16 September 2023 (UTC)

Well, it is my missing, of course for any number n the product of the (n-1) numbers starting from 2, divided by (n-1)!, is n, thus it can construct any positive integer n>=3, and if starting from 3, the product of the (n-2) numbers starting from 3, divided by (n-2)!, is n(n-1)/2, which contains infinitely many squares (and as you stated, contain no perfect m-th powers with m>2), thus the started number must be >=4

—— 36.234.121.52 (talk) 18:16, 16 September 2023 (UTC)

Find the smallest such prime number

There are 26 elements in the minimal set of “prime” strings in base 10:

{2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 66600049} (see https://oeis.org/A071062)

and the prime 1235607889460606009419 is the smallest prime containing all these 26 primes as subsequence. (see https://t5k.org/curios/page.php?short=1235607889460606009419)

Besides, there are 77 elements in the minimal set of “prime > 10” strings in base 10:

{11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027} (see https://oeis.org/A347819)

and what is the smallest prime containing all these 77 primes as subsequence? I searched “shortest common supersequence” with Google, but it seems that all these programs can handle only two strings to find their shortest common supersequence, how to find the shortest common supersequence to many strings? 36.234.121.52 (talk) 23:14, 15 September 2023 (UTC)

Using this program (found from here), the shortest common supersequence is 220000011317194666973799496495515501508150512221208766600049887881660000498578278218501558158015877555555555551557521805555514494095851281500000000000000000000000000002725772512277202018983646949200218005167615953474341600000495020729049001234991606498516666492215200007275787 (which is not prime).

Given the size, I don't expect it to be particularly easy to find a supersequence that is prime. LittlePuppers (talk) 23:47, 15 September 2023 (UTC)

This number has 276 digits, I think that it is possible to add one digit inside it to get a 277-digit prime, but you should check all supersequences with length 276 or 277, of these 77 primes. 36.234.121.52 (talk) 23:53, 15 September 2023 (UTC)

Note that technically the program is only an approximation algorithm with a proven approximation factor of 4 and a conjectured approximation factor of 2. GalacticShoe (talk) 00:27, 16 September 2023 (UTC)

Ah yep, that's right - I really wasn't reading the text on that page. I wondered why it was so fast. LittlePuppers (talk) 01:00, 16 September 2023 (UTC)

I think it's also worth noting that the definition of subsequence being used here is one that doesn't require contiguousness (e.g. in the same way 66600049 is a noncontiguous subsequence of 1235607889460606009419), while I believe that the program is specifically designed for contiguous subsequences. Whether this makes potential algorithms easier or harder to find/implement, I'm not sure. GalacticShoe (talk) 04:09, 16 September 2023 (UTC)

Ha, I didn't realize that either... that also changes it substantially. LittlePuppers (talk) 05:53, 16 September 2023 (UTC)

“Substring” requires contiguousness, while “subsequence” does not require, see longest common subsequence and longest common substring. Also, the 77 primes {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027} are the only primes > 10 which have no subsequence which is also a prime > 10 (I have a proof), while there are infinitely many primes > 10 which have no substring which is also a prime > 10, there are no infinite antichains for the subsequence ordering, while there can be infinite antichains for the substring ordering. 36.234.121.52 (talk) 15:53, 16 September 2023 (UTC)

I meant “shortest common supersequence” instead of “shortest common superstring”, see https://www.geeksforgeeks.org/shortest-common-supersequence/ and https://leetcode.com/problems/shortest-common-supersequence/ and https://www.codingninjas.com/studio/problem-details/shortest-supersequence_4244493, also online programs such as https://algorithm-visualizer.org/dynamic-programming/shortest-common-supersequence and https://p-library.com/o/scs/ but unfortunately all of them can only handle two strings. 36.234.122.29 (talk) 18:03, 17 September 2023 (UTC)

What is the smallest n such that there exists a holyhedron with n faces?

What is the smallest n such that there exists a holyhedron with n faces? If the exact value of n is still unknown, please give its lower bound and upper bound. 36.234.121.52 (talk) 23:48, 15 September 2023 (UTC)

Based on the holyhedron article and its MathWorld link, it would appear that the best upper bound is probably still the 492 face one constructed in 2003. GalacticShoe (talk) 04:10, 16 September 2023 (UTC)

Thanks. Are there known lower bound? It is clearly that 4, 5, 6, 7, … faces are not possible. 36.234.121.52 (talk) 15:48, 16 September 2023 (UTC)