Mad Numbers

Suppose we play the game Button Madness on an n-by-n board. Is it always possible to go to the all-green position starting from an arbitrary position? The answer turns out to be NO, and numbers n for which there are bad positions are called mad numbers. For example, 3 is mad.

Any multiple of a mad number is again mad, so the interesting ones are the mad numbers without proper mad divisors. Let us call them MAD.

62 MAD numbers below 10^9 are known, namely

#1: 3				(2^1+1)
#2: 5				(2^2+1)
#3: 17				(2^4+1)
#4: 31				(2^5-1)
#5: 127				(2^7-1)
#6: 257				(2^8+1)
#7: 511				(2^9-1)
#8: 683				(2^11+1)/3
#9: 2047			(2^11-1)
#10: 2731			(2^13+1)/3
#11: 3277			(2^14+1)/5
#12: 3641			(2^15+1)/9
#13: 8191			(2^13-1)
#14: 43691			(2^17+1)/3
#15: 52429			(2^18+1)/5
#16: 61681			(2^20+1)/17
#17: 65537			(2^16+1)
#18: 85489			(2^26+1)/785
#19: 131071			(2^17-1)
#20: 174763			(2^19+1)/3
#21: 178481			(2^23-1)/47
#22: 233017			(2^21+1)/9
#23: 253241			(2^26+1)/265
#24: 256999			(2^29-1)/2089
#25: 486737			(2^29-1)/1103
#26: 524287			(2^19-1)
#27: 704093			(2^30+1)/1525
#28: 838861			(2^22+1)/5
#29: 1016801			(2^25+1)/33
#30: 1082401			(2^25-1)/31
#31: 1657009			(2^27+1)/81
#32: 1838599			(2^27-1)/73
#33: 1965379			(2^36-1)/34965
#34: 2304167			(2^29-1)/233
#35: 2796203			(2^23+1)/3
#36: 3033169			(2^29+1)/177
#37: 3303821			(2^30+1)/325
#38: 3605429			(2^34+1)/4765
#39: 3705353			(2^35+1)/9273
#40: 6700417			(2^32+1)/641
#41: 8727391			(2^35-1)/3937
#42: 9335617			(2^36+1)/7361
complete up to n=10^7
#43: 13788017			(2^33-1)/623
#44: 15790321			(2^28+1)/17
#45: 19173961			(2^27-1)/7
#46: 21225581			(2^42+1)/207205
#47: 24214051			(2^35+1)/1419
#48: 25080101			(2^34+1)/685
#49: 25781083			(2^37+1)/5331
#50: 53353631			(2^33-1)/161
#51: 102964687			(2^45-1)/341713
#52: 120296677			(2^38+1)/2285
#53: 164511353			(2^41-1)/13367
#54: 207207011			(2^45+1)/169803
#55: 240068041			(2^38+1)/1145
#56: 256957153			(2^45-1)/136927
#57: 464955857			(2^46+1)/151345
#58: 598781009			(2^42+1)/7345
#59: 616318177			(2^37-1)/223
#60: 715827883			(2^31+1)/3
#61: 905040953			(2^43-1)/9719
#62: 993089953			(2^54+1)/18139745
complete up to n=10^9 for pmorder < 200

Aart has some unpublished theory. It implies that (2^m-1)/d and (2^m+1)/d are mad when these are integral and d is sufficiently small. If such numbers are also prime, then they are MAD. For example, (2^43+1)/3 = 2932031007403 is MAD, and so is every Mersenne prime larger than 7, and every Fermat prime. There are infinitely many MAD numbers.

See also the very similar list for the Lights Out! version of this game. There is also information on a rectangular board.