 Conflux
closes Mar 31
Will I learn of a “nice number” besides 69 by the end of March 2023? (revised definition)
8%
chance

69^2 = 4761

69^3 = 328509

As you can see, the square and cube of 69, in base 10, contain all the digits with no repeats. In general, a nice number, in some base, is a real, natural number whose square and cube, written in that base, contain all the digits in that base with no repeats. Only normal positive integer bases are considered for this market.

So far, this is the only nice number I know of. I suspect that there are an infinite number, but they only start appearing around base 120 to 130; I checked up to around base 30.

I discuss this more in my blog post http://tinyurl.com/confluxblog/post/is-69-unique.

UPDATE 1/30/23: I wrote an update blog post! http://tinyurl.com/confluxblog/post/progress-update-on-the-search-for-nice-numbers

Anyway, hopefully this market inspires you to do some research into finding nice numbers, or to find someone else online who has!

I may also provide mana rewards for partial results.

Note: The original version of this market, embedded below, had a poorly worded definition which included negative numbers such as -69 (and more arguably complex numbers such as 69i and -69i). I've cancelled that market (resolved it N/A) and made this replacement. Still, the old one contains many comments with progress on the problem and cool related results! Along with discussion over the N/A resolution.

My new, subject-to-revision policy based on this dispute: In the rare event of a conflict between my resolution criteria and the common-sense, consensus spirit of the market, I may resolve it according to the market's spirit or N/A, probably after discussion.

Sort by: Isaac Kingis predicting YES at 11%

I'm curious whether this market's low probability is coming more from "this is a really hard problem in principle" or "we don't have enough time to solve it right now", so I made one with a longer time frame: Confluxis predicting NO at 11%

@IsaacKing I think mostly the former - we need more theoretical insights, and the low-hanging fruit is probably gone.  Confluxbought Ṁ69 of NO

@Conflux It's actually in second place for Confluxis predicting NO at 11%

I should also mention that the post heavily features the cool insights made by Manifold users @Cadence @JoshuaB @Yev @JoshuaB @halfaswiftie @JoshuaB @cat @JoshuaB @wasabipesto @BoltonBailey I've issued a bounty - come search with me and get M\$!
https://discordapp.com/channels/915138780216823849/1067590450619351110 Just found an off-by-one in base 40, much higher than I thought I would:

4134931983708
Square: [15, 36, 37, 20, 4, 0, 25, 2, 18, 29, 8, 21, 7, 13, 11, 24]
Cube: [10, 1, 34, 31, 23, 3, 14, 26, 16, 19, 33, 6, 38, 30, 5, 28, 35, 17, 9, 6, 22, 39, 12, 32]
39/40 unique (6 repeats, 27 is missing)  Note the point where the numbers thin out - the sequential search group is only ~60% through base 40. The outlier near 4e12 is our new friend. Дмитрий Зеленскийis predicting YES at 12%

I think it might be obvious and/or useless but thought I'd weigh in with this:

If a number x is nice, then the sum of digits of x^2 and x^3 in base b is p(p-1)/2.

h(x[,b])=indicator(f(x,b)=b(b-1)/2)
f(x[,b])=g(x^2,b)+g(x^3,b)
g(x[,b]) is the function of sum of a number's digits in base b

So, h(x) here should be 1 for all nice numbers (if only I could manage to make it show the dots normally...): https://www.desmos.com/Calculator/yvtuzgiryl; https://www.desmos.com/Calculator/zqv4n1ykwq; https://www.desmos.com/Calculator/wmmkiyyi24 (of course, the online calculator does not actually properly do this for the big bases).

Note that the converse is not true: not all of the numbers where h(x)=1 are nice (obviously) - for instance, h(72,10) and h(78,10) is 1, and so is h(21, 8) (21 is written in base 10, that would be 25 base 8). But, if there is an efficient way to calculate h(x), this could shorten the brute-force search. Confluxis predicting NO at 12%

@b575 Oops, somehow missed this comment! If I'm not misunderstanding, I think this gets you the improvement of residue filtering (couple orders of magnitude), but nothing more. @cat 's observation actually makes me much more optimistic in a solution. It occurs to me that we might be able to take much better advantage of the algebraic structure of the problem to find a solution (potentially a solution where base b is extremely high, but that still counts)

Here is another ideas future market for this approach, lmk if you spot any improvements to the algorithm Bolton Baileybought Ṁ55 of YES

@BoltonBailey Note this doesn't work out heuristically. Supposing I restrict myself to bases of the form b = 5k, the square has 2k bigits and the cube has 3k bigits. If I take a "random" value for the square and the cube, and I cube the square and square the cube I get a 1-in-b^(6k) chance of them being equal, but I only have O(k^10) options for the lengths. Perhaps there's an algebraic reason for it to still work out though. catis predicting NO at 17%

I don't think it's very likely that finding another nice number is computationally feasible (though I'd be happy to be proved wrong!), but I thought I'd share one thing I figured out about this problem:
--

Theorem: If the base is of the form b = 4k+3, there are no nice numbers.

Proof: Suppose x is a nice number in base b. Then

x^2 + x^3 = 0 + 1 + ... + (b-1) (mod b-1)

by the usual "digital sum" argument used to reduce numbers mod 9 in base 10. But if b = 4k+3 then

0 + 1 + ... + (b-1) = (2k+1)(4k+3)

is odd, while b-1 = 4k+2 is even. So this would imply that x^2 + x^3 is odd, but all numbers of the form x^2 + x^3 are even. Contradiction.

--

This type of argument in reverse also gives an improvement to the heuristics when b is NOT of the form 4k+3: if b-1 is divisible by a large square, then it is more likely that x^2 + x^3 is a multiple of b-1, and hence more likely that the final digit computed will be distinct from all the others. So for instance a number in base b=122 should be roughly 11 times more likely to be nice than the naive heuristic suggests, since x being a multiple of 11 is sufficient to make the digital sum of x^2 + x^3 correct (mod b-1). Confluxis predicting NO at 15%

@cat Thank you so much for this insight! I'd give you an M\$69 bounty if you DM me on Discord.

I hadn't thought about digital sums at all before this, but this line of thinking goes a long way into improving the heuristics for this problem, and also demystifying some of @Yev's weird results on quasi-nice number density! Hopefully all the math I write below is clear and correct.

If anyone's curious why digital sums work, some quick intuition: 1 and 10 differ by 9, and in any base b, 1 and 10 will differ by b-1. So changing the place value of a digit does not affect the residue (aka remainder) mod b-1.

In particular, by considering the residue of x^2+x^3 mod b-1, and comparing to the residue of 0+1+...+(b-1) = b(b-1)/2 (triangular numbers formula - this residue is 0 for even bases and (b-1)/2 for odd bases) we can generate the list of possible residues for a base. So like for base 10, the residue mod 9 must be 0, 3, 6, or 8, because 0^2+0^3 = 3^2+3^3 = 6^2+6^3 = 8^2+8^3 = 0 mod 9, and 10 is even so we want a residue of 0. There are some cool patterns in the list of possible residues: for example, for even bases, 0 and b-1 are always possible, and possible residues must be 0 or -1 mod each other prime factor of the base.

But importantly: how much information does it provide when the residue is correct? Well, if we have some x^2 and x^3 that we want to check for niceness, and we have all the digits except for one but know the residue, that will generally tell us the last digit (one exception: if the last digit is 0 or b-1, it's ambiguous, because remember we're doing this all mod b-1). Anyway, that one digit naively would've had a 1/b chance of being correct, so we can multiply the chance of niceness by b.

Anyway, Yev got us some data on quasi-nice numbers (where x and x^2 have all the digits in the base) and actually found a bunch, and there was some weirdness where the quantities didn't quite match the heuristics. However, I was able to calculate the number of residues that work and apply a correction factor to the heuristics, and this makes them fit the data much better!

https://www.desmos.com/calculator/0uyzchjbqn (green = new heuristic, purple = old heuristic) Confluxis predicting NO at 15%

@Conflux Oh also, weird coincidence: The sequence of number of residues that work for niceness (x^2, x^3) in each base is not in the OEIS, and neither is quasi-niceness (x, x^2), but all the quasi-niceness terms after the first are even, and dividing the sequence by two is in the OEIS ... as "Number of primitive Pythagorean triangles with leg n."! Weird. https://oeis.org/A024361 catis predicting NO at 15%

@Conflux Yes, this is what I meant by my last paragraph, I was just too lazy to carefully write out anything other than observing that b-1 being divisible by a large square is helpful. :P But it is true that b-1 being divisible by a bunch of small primes is also helpful for the same reason, it means that x^2+x^3 = b(b-1)/2 (mod b-1) has more solutions.

Incidentally, with this heuristic I'm getting about a 15% chance of there existing another nice number with b <= 100 (with a third of that coming from b=100 itself). So to beat the current market you'd need to be able to search up to roughly base 100. Confluxis predicting NO at 16%

@cat I was able to confirm this value of 15% by base 100, so seems like we're doing the same thing!

With current heuristics, base 100 has a search space on the order of 10^37 or 10^38. Дмитрий Зеленскийis predicting YES at 12%

@cat @Conflux By the same token, b=3k+2 is problematic? Digital sum is (3k+2)(3k+1)/2=(9k2+9k+2)/2=(9k2+9k)/2+2/2=9k(k+1)/2+1, which is 1 mod 3. But x^2+x^3 is either 0 mod 3 (if x is 0 mod 3 or 2 mod 3) or 2 mod 3 (if x is 1 mod 3). Дмитрий Зеленскийis predicting YES at 12%

Same pertains to b=7k+4 (digital sum is 6 mod 3 while x^2+x^3 are 0, 1, 2, 3, or 5 mod 7). Дмитрий Зеленскийis predicting YES at 12%

6 mod 7, of course!
Likewise, b=11k+4 and b=11k+8 give digital sum that's 6 mod 11 and b=11k+6 gives digital sum that's 4 mod 11 while x^2+x^3(=(x^2)(1+x)) are 0, 2, 1, 3, 3, 7, 10, 7, 4 or 7 mod 11 (repeats and order are intentional).

The general form of the check is that b=qk+i (for i=(1,...,q-1)) provides a sequence of digital sums that is equivalent mod q to the (0,1,3,6,10,15,21...) mod q, which is then to be cross-compared to (j^2)(j+1) mod q for j=1,...,q-2 (that sequence starts as 2, 12, 36, 80, 150, 252, 392, 576, 810, 1100...) Confluxis predicting NO at 11%

@b575 Convincing but false! I knew it couldn’t be quite right because it applied to quasi-nice numbers (when x and x^2 have all digits), and those do exist for 2 mod 3 bases, but it took me a minute to figure out why: when you’re looking at a modulus besides base-1, rearranging digits will affect the residue, so you can’t just calculate it for b(b-1)/2 and call it a day.

174 is quasi-nice in base 8 (as 256 and 73104) for instance. (174 + 174^2) mod 3 = 0 while 0+1+2+3+4+5+6+7 mod 3 = 1, and that’s fine because the digits are rearranged. Дмитрий Зеленскийis predicting YES at 11%

@Conflux Huh. Yeah. I guess I jumped to conclusions a bit. Joshuais predicting YES at 18%

Here’s some finds for related problems!

I’ve found some doubly nice numbers (numbers that use all the digits twice)!

(In all of these bases, there might be more. I just found the smallest example)

In base 7

335^2 = 153154

335^3 = 62003246

In base 10:

6534^2 = 42693156

6534^3 = 278957081304

All examples from here on out are written in base 10 (for my convenience)... in Base 14 (1641939); Base 15 (7218806); Base 16 (32006130); and in Base 17 (114542504).

Triply nice numbers: Base 4 (23); Base 9 (72150); Base 10 (497375); Base 13 (231851201)

Quadruply nice numbers: Base 5 (383); Base 6 (3869); Base 7 (32891); Base 8 (310807); Base 10 (46839081); Base 11 (711327934); Base 12 (11818766421)

Quintuply nice numbers: Base 4 (170); Base 5 (1893); Base 6 (30305); Base 8 (8597007); Base 9 (186446342); Base 10 (4641856941)

Sextuply nice numbers: Base 4 (633); Base 5 (9147); Base 7 (5816984); Base 8 (268482395); Base 9 (10464286792); Base 10 (464162827242)

Anyways, a nifty observation is that there’s an example in Base 10 for all n-ply nice numbers for n between 1 and 6 (which is the highest number that my program can reasonably check base 10)

There are no more semi-nice numbers (mentioned here and defined by the “Nice Number Authority™” a.k.a. @Conflux as “a non-nice number that would be nice if you allow formatting numbers with leading zeroes”), besides the original found by @Yev here, in any base between 2 and 32.

Also, for the actual question: there are no nice numbers (besides 69) in base 35 or below! Here's a market about whether a particular approach will work. Bid it up to encourage me to implement it before March. Yevbought Ṁ50 of NO

Does @JoshuaB know something we don't? 🤔 Joshuabought Ṁ20 of NO

@Yev Nah, not yet! Mostly betting YES as a precommitment to look for nice numbers. Yevis predicting NO at 20%

@JoshuaB I was going to look for them, but I probably won't since I have so many NO shares. Confluxis predicting NO at 17%

@Yev :/ Isaac Kingis predicting YES at 17%

@Conflux It's fine, Yev's NO shares just encourage someone else to look for them instead.