A new conjecture concerning perfect powers

[marcokrt]

In the second half of April 2022, I submitted to the OEIS a new sequence of integers concerning perfect powers (see https://oeis.org/A353025), listing the smallest perfect powers written as the concatenation of any permutation of the integers from $1$ to $n$ (for any given $n$).
Now, there are $94$ perfect squares that are smaller than $10^17$ and many others between $10^22$ and $10^29$, but no perfect power above 2 has been detected after several hours of computations on a standard CPU (moreover, the friend of mine who performed the mentioned search is still running his code hoping to find a cube consisting of $35 digits$, but no counterexample to the following conjecture has been found yet):


Conjecture: All the terms of the OEIS sequence A353025 which are greater than $1$ are perfect squares and nothing else (no cube, no square of square, and so forth).


The smallest counterexample (if any) should necessarily be greater than $1.01*10^34$ and it must be congruent modulo $9$ to $0$ or $1$ (for details, see DOI:10.13140/RG.2.2.30313.77921/1).


Thanks in advance to everyone and good luck!

[LaurV]

Anything wrong with those 94 numbers, or my brain is farting now?

How do you generate those permutations, if there are more than 10 digits? Can you split 10 and 11, and 12, etc, and change the order of the digits, treating them as individuals, or you must always keep them together?

In the first case, I believe there should be more numbers in the list, and in the last, I believe there are some typos in the list. For example, I can not comprehend how the 94th (the first I was looking at, you know, I wanted to see the biggest one! ) does represent a permutation of the numbers 1 to 13, if you don't mess with each digit individually, and even so...

94 95641012181133721

Taking our all the digits between 4 and 9 inclusive (as they must be individual digits, i.e. single digits numbers, because the max used is 13), you are left with either too many 3s or too many 1s... As there is no 37 or 33 or 81, you can't have 11-3-3, and if you have 1-13-3, than what about the 1 at the end and the 1 before 8? (there is no 21 either, in both cases, the max is 13).

[charybdis]

Your conjecture is almost certainly false, but we don't have enough computing power to find a counterexample.

Consider permutations of the numbers from 1 to 43. The digit sum is 1 mod 9, so such a number could theoretically be a cube. Such numbers have 77 digits. The probability that a randomly chosen 77-digit number is a cube is (number of cubes with 77 digits)/(number of numbers with 77 digits) = (10^(77/3) - 10^(76/3))/(9*10^76) = 1/(3.62*10^51). But the number of permutations is 43! = 6.04*10^52. In other words, there should be roughly (6.04*10^52)/(3.62*10^51) ≈ 17 cubes which are permutations of the numbers from 1 to 43, and it's overwhelmingly likely that at least one such counterexample exists.

Edit: silly me, of course we aren't picking randomly, we're picking numbers that are 1 mod 9, and these are 6 times more likely to be cubes than randomly chosen numbers... so multiply that 17 by 6 to get about 100 counterexamples.

You can run the same calculation to see that the first counterexample probably occurs for permutations from 1 up to one of 34, 35, 36 or 37. This is far too large for finding one to be feasible.

Eventually you'll get fourth powers, and fifth powers, and so on. But those are even further out of reach.

[marcokrt]

Originally Posted by LaurV

Anything wrong with those 94 numbers, or my brain is farting now?

How do you generate those permutations, if there are more than 10 digits? Can you split 10 and 11, and 12, etc, and change the order of the digits, treating them as individuals, or you must always keep them together?

No, you cannot... otherwise we can easily find many "small" counterexamples, such as 2326^3, 308344^3, 416308^3, 22330489^3, 23584549^3, 25262887^3, and so forth.

Originally Posted by LaurV

In the first case, I believe there should be more numbers in the list, and in the last, I believe there are some typos in the list. For example, I can not comprehend how the 94th (the first I was looking at, you know, I wanted to see the biggest one! ) does represent a permutation of the numbers 1 to 13, if you don't mess with each digit individually, and even so...

Taking our all the digits between 4 and 9 inclusive (as they must be individual digits, i.e. single digits numbers, because the max used is 13), you are left with either too many 3s or too many 1s... As there is no 37 or 33 or 81, you can't have 11-3-3, and if you have 1-13-3, than what about the 1 at the end and the 1 before 8? (there is no 21 either, in both cases, the max is 13).

Good call, I've recently pointed out the "false positive" issue to the code creator, but I noted this for the cubes search permutating the string 123...2122. The conjecture is published on the OEIS together with the sequence A353025, so we would check also the b-file and the terms one by one. On the other hand, the provided code cannot skip any perfect power candidate, so we are 100% sure that ther isn't any perfect power above 2 among the terms of A353025 which are smaller than 10^34.
Any volunteers here to improve the given code and/or check which candidates among the given 94 squares really belong to A353025?

[marcokrt]

Originally Posted by charybdis

Your conjecture is almost certainly false, but we don't have enough computing power to find a counterexample.

Consider permutations of the numbers from 1 to 43. The digit sum is 1 mod 9, so such a number could theoretically be a cube. Such numbers have 77 digits. The probability that a randomly chosen 77-digit number is a cube is (number of cubes with 77 digits)/(number of numbers with 77 digits) = (10^(77/3) - 10^(76/3))/(9*10^76) = 1/(3.62*10^51). But the number of permutations is 43! = 6.04*10^52. In other words, there should be roughly (6.04*10^52)/(3.62*10^51) ≈ 17 cubes which are permutations of the numbers from 1 to 43, and it's overwhelmingly likely that at least one such counterexample exists.

Edit: silly me, of course we aren't picking randomly, we're picking numbers that are 1 mod 9, and these are 6 times more likely to be cubes than randomly chosen numbers... so multiply that 17 by 6 to get about 100 counterexamples.

You can run the same calculation to see that the first counterexample probably occurs for permutations from 1 up to one of 34, 35, 36 or 37. This is far too large for finding one to be feasible.

Eventually you'll get fourth powers, and fifth powers, and so on. But those are even further out of reach.

This would be true if we assume that the probability to find a cube is equally distributed among the set of such candidates... yeah, a counterexample could theoretically exist, but it would be awesome to prove this (or to constructively find a perfect power above 2 by performing a random search there, hoping to find one of such unicorns).

In the end, I think that this could be an interesting comment to post on the OEIS too... and also a valid test to streach our computational power in the future, in order to see who will be able to find the first counterexample (if any). Moreover, the smallest perfect power >2 belonging to A353025 would be a good OEIS sequence by itself, giving it as "decimal expansion" of that number (keywords nonn, fini, full).

[VBCurtis]

You really ought to consider how many [expected] trials it would take to find one counterexample. I mean, Charybdis spelled it out for you, but you seem to have ignored him. A one in 10^50 chance per trial... c'mon.

[marcokrt]

Originally Posted by VBCurtis

You really ought to consider how many [expected] trials it would take to find one counterexample. I mean, Charybdis spelled it out for you, but you seem to have ignored him. A one in 10^50 chance per trial... c'mon.

I know, by brute force actually it is very unlikely to find anything in a dozen years, using the current CPUs available. For this reason it would be interesting to work on the conjecture using mathematics or waiting quantum computers, maybe? Who knows... in the meantime the conjecture has not been disproved, as far as we know.

Finally, have someboby of you taken a look at Kashihara's conjecture (since 1996)? It states that (according to its author) there isn't any term belonging to the OEIS sequence A001292 which is a perfect power (disregarding A001292(1) = 1). We have checked it up to 10^1235 and we have not found any counteraxample.

[marcokrt]

P.S. The code writer (Aldo) has manually checked all the old b-file outputs and we have exactly 72 perfect squares belonging to A353025 which are smaller than 10191583652124141311716.


Candidates 1-43 are ok. Then, we have


10-13-5-6-8-1-7-4-2-3-11-12-9 --> 44
- XX 45 10145718212113936
46 10-2-7-3-4-11-12-13-1-8-5-6-9 --> 45
47 10-3-9-1-4-12-11-3-8-5-2-1-7-6 --> 46
48 10-6-9-4-8-7-13-3-11-5-2-12-1 --> 47
49 10-7-13-2-9-3-5-12-4-11-6-8-1 --> 48
50 10-9-4-7-2-8-12-11-1-13-5-3-6 --> 49
- XX 51 11013125389146721
- XX 52 11038121341751296
- XX 53 11053681319247121
- XX 54 11213173481106529
- XX 55 11213472311091856
56 11-2-13-7-4-8-6-9-5-3-10-12-1 --> 50
- XX 57 11214101328395716
- XX 58 11291351028471361
59 11-3-1-8-9-12-10-5-4-2-13-7-6 --> 51
- XX 60 11328110357491216
- XX 61 11361038197125241
62 11-6-13-10-5-12-8-3-1-7-9-2-4 --> 52
63 11-8-3-13-7-5-6-1-2-10-4-12-9 --> 53
64 11-8-6-7-2-13-10-3-9-5-4-12-1 --> 54
65 12-13-10-4-7-8-11-1-5-3-2-9-6 --> 55
66 12-2-10-5-3-11-13-6-1-7-9-8-4 --> 56
67 12-2-9-13-3-11-5-4-10-8-1-7-6 --> 57
- XX 68 12311021567131849
69 1-2-3-7-13-6-8-11-5-12-9-10-4 --> 58
- XX 70 12511389126371041
71 12-5-9-8-4-11-13-2-1-10-7-3-6 --> 59
- XX 72 12741133825910161
- XX 73 12859110713124361
74 12-8-6-11-13-1-7-3-2-9-5-10-4 --> 60
75 13-10-11-1-8-6-12-5-7-3-9-2-4 --> 61
- XX 76 13318759261211041
- XX 77 13751214611018329
- XX 78 15113103721812496
- XX 79 16213112510379841
- XX 80 16798112351131024
- XX 81 18132127110314569
- XX 82 18351311069274121
83 3-13-2-9-11-6-1-12-10-7-5-8-4 --> 62
- XX 84 32121784510113169
85 3-9-8-1-13-6-2-12-7-5-11-10-4 --> 63
- XX 86 43139171611081225
- XX 87 51371123211048169
- XX 88 51611037284113129
89 5-8-9-11-12-4-13-10-6-7-3-2-1 --> 64
90 7-11-2-12-5-13-8-3-6-9-10-4-1 --> 65
91 7-12-8-9-6-11-4-3-13-1-10-2-5 --> 66
- XX 92 72511393110124816
93 8-3-7-6-11-13-4-2-1-10-5-12-9 --> 67
94 9-13-8-4-7-1-3-2-12-5-10-11-6 --> 68
- XX 95 95641012181133721
96 10-11-13-8-2-4-14-5-1-9-16-15-7-12-3-6 --> 69
- XX 97 10112141913836245151716
- XX 98 10113161253891156147241
- XX 99 10143413198521612115716
100 10-15-2-12-11-9-1-7-5-14-8-3-6-4-13-16 --> 70
- XX 101 10154811423137561916121
102 10-16-2-11-15-8-6-3-12-9-5-7-13-14-4-1 --> 71
- XX 103 10191516146128311354721
104 10-1-9-15-8-3-6-5-2-12-4-14-13-11-7-16 --> 72

For my conjecture, we should disregard A353025(1) = 1, thus we have 71 perfect squares in the range (2, 10191583652124141311716], while the search for cubes among all the permutations of 123...2122 is almost ended (with no counterexample found and a couple of hours left). No perfect powers above 2 up to 10^34 (no cube, no square of square, etc.).

[marcokrt]

Originally Posted by charybdis

Your conjecture is almost certainly false, but we don't have enough computing power to find a counterexample.

Consider permutations of the numbers from 1 to 43. The digit sum is 1 mod 9, so such a number could theoretically be a cube. Such numbers have 77 digits. The probability that a randomly chosen 77-digit number is a cube is (number of cubes with 77 digits)/(number of numbers with 77 digits) = (10^(77/3) - 10^(76/3))/(9*10^76) = 1/(3.62*10^51). But the number of permutations is 43! = 6.04*10^52. In other words, there should be roughly (6.04*10^52)/(3.62*10^51) ≈ 17 cubes which are permutations of the numbers from 1 to 43, and it's overwhelmingly likely that at least one such counterexample exists.

Edit: silly me, of course we aren't picking randomly, we're picking numbers that are 1 mod 9, and these are 6 times more likely to be cubes than randomly chosen numbers... so multiply that 17 by 6 to get about 100 counterexamples.

You can run the same calculation to see that the first counterexample probably occurs for permutations from 1 up to one of 34, 35, 36 or 37. This is far too large for finding one to be feasible.

Eventually you'll get fourth powers, and fifth powers, and so on. But those are even further out of reach.

Interesting argument, but there are additional constraints that we are missing by assuming an uniform distribution of cubes among numbers that are not consecutive integers (I am not saying that a counterexample wouldn't be absolutely resonable in this range)... (e.g., let us take any subset of the following set of numbers in the range (1-99) {2, 5, 6, 10, 14, 15, 18, 20, 22, 26, 30, 34, 35, 38, 40, 42, 45, 46,50, 54, 55, 58, 60, 62, 65, 66, 70, 74, 78, 80, 82, 85, 86, 90, 94, 95, 98} and then let us concatenate every permutation of the selected subset... how many perfect cubes (from 1 to 70+ digits) will we find? None, since no cube can belong to any of the above mentioned congruence classes modulo 100.

It is just an example to show that an interesting probabilistic argument cannot disprove this conjecture by itself, but it remains a good point to working on (IMHO).

[charybdis]

Originally Posted by marcokrt

Interesting argument, but there are additional constraints that we are missing by assuming an uniform distribution of cubes among numbers that are not consecutive integers (I am not saying that a counterexample wouldn't be absolutely resonable in this range)... (e.g., let us take any subset of the following set of numbers in the range (1-99) {2, 5, 6, 10, 14, 15, 18, 20, 22, 26, 30, 34, 35, 38, 40, 42, 45, 46,50, 54, 55, 58, 60, 62, 65, 66, 70, 74, 78, 80, 82, 85, 86, 90, 94, 95, 98} and then let us concatenate them... how many perfect cubes (from 1 to 70+ digits) will we found? None, since no cube can belong to any of the above mentioned congruence classes modulo 100.

It is just an example to show that an interesting probabilistic argument cannot disprove this conjecture by itself, but it remains a good point to working on (IMHO).

I never intended my argument to be a proof, and there isn't any way to turn it into one.

Anyway, you ask about whether it's safe to assume that our permutations have the same chance of being cubes as randomly chosen numbers do. There are two things that can throw this off:

(a) Cubes get gradually rarer as we go up through N-digit numbers. Permutations beginning with a 9 will also usually be rarer than those beginning with a 1, but the distribution isn't the same; there will be a sharp cutoff in the frequency of permutations.
How much does this affect our calculations? Not much. It will change the probabilities somewhat, but won't change the fact that by the time we get to permutations of 1-43 we are basically guaranteed a cube.

(b) Modular considerations. You already noted one, namely that permutations and cubes are both unevenly distributed mod 9. I already took this into account in my calculations. The uneven distributions of both permutations and cubes mod powers of 10 may also change the expectations by some constant factor. But there's nothing about our 1-n permutations that could make cubes wildly less likely or impossible, except for the mod 9 condition which we can easily take care of.
Your example above is totally contrived and I think you understand that.

Changing the expectations by a constant factor may change where we expect the counterexample to occur, but there are expected to be infinitely many counterexamples, so if you're trying to prove the conjecture true then a constant won't be enough.

[note: there are of course other ways that we might be able to tell that a number can't be a cube, e.g. if it has an algebraic factorization then maybe the factors have to be coprime and can't all be cubes, but they aren't relevant here]

This is one of many, many problems where "the heuristic suggests that X happens infinitely often, so we should expect X to happen infinitely often, unless there's some obvious reason why it can't".
Simple (proved) example: Dirichlet's theorem. There are infinitely many primes of the form a mod n, unless a isn't coprime to n.
Unproved examples: basically any unsolved conjecture pertaining to primes (twin prime conjecture, infinitely many Mersennes, Sierpinski conjecture and its generalizations...)

[marcokrt]

Originally Posted by charybdis

I never intended my argument to be a proof, and there isn't any way to turn it into one.

Anyway, you ask about whether it's safe to assume that our permutations have the same chance of being cubes as randomly chosen numbers do. There are two things that can throw this off:

(a) Cubes get gradually rarer as we go up through N-digit numbers. Permutations beginning with a 9 will also usually be rarer than those beginning with a 1, but the distribution isn't the same; there will be a sharp cutoff in the frequency of permutations.
How much does this affect our calculations? Not much. It will change the probabilities somewhat, but won't change the fact that by the time we get to permutations of 1-43 we are basically guaranteed a cube.

(b) Modular considerations. You already noted one, namely that permutations and cubes are both unevenly distributed mod 9. I already took this into account in my calculations. The uneven distributions of both permutations and cubes mod powers of 10 may also change the expectations by some constant factor. But there's nothing about our 1-n permutations that could make cubes wildly less likely or impossible, except for the mod 9 condition which we can easily take care of.
Your example above is totally contrived and I think you understand that.

Changing the expectations by a constant factor may change where we expect the counterexample to occur, but there are expected to be infinitely many counterexamples, so if you're trying to prove the conjecture true then a constant won't be enough.

[note: there are of course other ways that we might be able to tell that a number can't be a cube, e.g. if it has an algebraic factorization then maybe the factors have to be coprime and can't all be cubes, but they aren't relevant here]

This is one of many, many problems where "the heuristic suggests that X happens infinitely often, so we should expect X to happen infinitely often, unless there's some obvious reason why it can't".
Simple (proved) example: Dirichlet's theorem. There are infinitely many primes of the form a mod n, unless a isn't coprime to n.
Unproved examples: basically any unsolved conjecture pertaining to primes (twin prime conjecture, infinitely many Mersennes, Sierpinski conjecture and its generalizations...)

Your probabilistic argument is good, as I've already said. My point is that we do not know whether or not there are additional constraints (unknown by us right now) which could drop the distribution of cubes or prevent a perfect power above two to be a term of A353025, but (since we don't know any of these hypotetical unknown constraints) we have only two solid arguments: several perfect squares up to 10^34 or 10^36 (in a few hours) and no cube, and a probabilistic argument that give us 100% chances to get one (infinitely many) perfect power(s) above 2 under the additional condition to assume that there are no fundamental unknown constraints which are able to substantially modify the internal probability distribution or prevent collisions to happen at all.
Thus, the conjecture could also been reverted and say: "You conjecture that there are infinitely many cubes belonging to A353025" and it is absolutely reasonable, even if we are not able to find any of those unicorns... a Schrödinger cat which you assume 100% dead (which does not mean that it cannot be alive) and I conjectured to be alive until we are able to look inside the box.

(e.g., we could say that the probability that a random triangle has a 108° degree interior angle is 0%, but we could easily provide infinitely many triangles of this kind).

Moreover, there are not sum(j=1, n)j! terms up to the biggest permutation of 1_2_3_..._(n-1)_n (but less than that), since the same number can occur from different permutations (just to point out it, but this is a minor argument).