# Counting puzzle #1: Function combinations

Not in conjunction with my function optimization puzzles, also sorry for the extremely difficult discrete mathematics puzzle

So as you may or may not know, I have recently uploaded 2 function optimization puzzles which were only part of the inspiration for this puzzle. The rest of the inspiration mostly came from this comment from @AxiomaticSystem: I know this was supposed to refer to my minimum function optimization puzzles, but I want to try something here before doing that. Here is the puzzle I have created here:

Let\begin{align}f(n):=&\,n^2\\g(n):=&\,2n\\h(n):=&\,4n+1\end{align}and let set $$\mathbb S$$ be the set of pos. integers that can be achieved by applying any combination of $$f$$s, $$g$$s, and $$h$$s to 0. How many pos. integers $$\le2048$$ are in $$\mathbb S$$?

### Things to mention

1. Partial answers are 100% allowed and are going to be encouraged on this question! This is because this is a really difficult problem and I don't want to discourage anyone from answering.
2. This took me around 1.5 hours to solve{1}, so I have been able to verify that there is an answer that can be reached for this puzzle.
3. To get the $$\color{green}✓$$, you have to show your work on how you got all of the numbers and the final answer.

Hint:

This is also somewhat based off of Blackpenredpen's modification of a 2020 Oxford math admissions question, so this screenshot may come in handy when coming up with a strategy to solve it (from a deleted question of mine on Mathematics.SE that was asking if my solution to the aforementioned problem was correct): {1}without a brute force algorithm (I can't program that well), although I think those are allowed under the rules that I have stated as long as every number in $$\mathbb S$$ is printed and the alg. is given, although please try to solve it yourself first.

• I really don't think you need the not in conjunction with thing, because there's very little ambiguity or doubt that [puzzle x] goes with [puzzle y]. (As your titles are already always helpfully marked.)
– CDR
Nov 16 at 22:22

Programmed solution:

There are $$274$$ numbers in $$\mathbb S$$

These numbers are listed below, along with the function that produces them.

#1: 1 = h(0)
#2: 2 = g(1)
#3: 4 = g(2)
#4: 5 = h(1)
#5: 8 = g(4)
#6: 9 = h(2)
#7: 10 = g(5)
#8: 16 = g(8)
#9: 17 = h(4)
#10: 18 = g(9)
#11: 20 = g(10)
#12: 21 = h(5)
#13: 25 = f(5)
#14: 32 = g(16)
#15: 33 = h(8)
#16: 34 = g(17)
#17: 36 = g(18)
#18: 37 = h(9)
#19: 40 = g(20)
#20: 41 = h(10)
#21: 42 = g(21)
#22: 50 = g(25)
#23: 64 = g(32)
#24: 65 = h(16)
#25: 66 = g(33)
#26: 68 = g(34)
#27: 69 = h(17)
#28: 72 = g(36)
#29: 73 = h(18)
#30: 74 = g(37)
#31: 80 = g(40)
#32: 81 = h(20)
#33: 82 = g(41)
#34: 84 = g(42)
#35: 85 = h(21)
#36: 100 = g(50)
#37: 101 = h(25)
#38: 128 = g(64)
#39: 129 = h(32)
#40: 130 = g(65)
#41: 132 = g(66)
#42: 133 = h(33)
#43: 136 = g(68)
#44: 137 = h(34)
#45: 138 = g(69)
#46: 144 = g(72)
#47: 145 = h(36)
#48: 146 = g(73)
#49: 148 = g(74)
#50: 149 = h(37)
#51: 160 = g(80)
#52: 161 = h(40)
#53: 162 = g(81)
#54: 164 = g(82)
#55: 165 = h(41)
#56: 168 = g(84)
#57: 169 = h(42)
#58: 170 = g(85)
#59: 200 = g(100)
#60: 201 = h(50)
#61: 202 = g(101)
#62: 256 = g(128)
#63: 257 = h(64)
#64: 258 = g(129)
#65: 260 = g(130)
#66: 261 = h(65)
#67: 264 = g(132)
#68: 265 = h(66)
#69: 266 = g(133)
#70: 272 = g(136)
#71: 273 = h(68)
#72: 274 = g(137)
#73: 276 = g(138)
#74: 277 = h(69)
#75: 288 = g(144)
#76: 289 = h(72)
#77: 290 = g(145)
#78: 292 = g(146)
#79: 293 = h(73)
#80: 296 = g(148)
#81: 297 = h(74)
#82: 298 = g(149)
#83: 320 = g(160)
#84: 321 = h(80)
#85: 322 = g(161)
#86: 324 = g(162)
#87: 325 = h(81)
#88: 328 = g(164)
#89: 329 = h(82)
#90: 330 = g(165)
#91: 336 = g(168)
#92: 337 = h(84)
#93: 338 = g(169)
#94: 340 = g(170)
#95: 341 = h(85)
#96: 400 = g(200)
#97: 401 = h(100)
#98: 402 = g(201)
#99: 404 = g(202)
#100: 405 = h(101)
#101: 441 = f(21)
#102: 512 = g(256)
#103: 513 = h(128)
#104: 514 = g(257)
#105: 516 = g(258)
#106: 517 = h(129)
#107: 520 = g(260)
#108: 521 = h(130)
#109: 522 = g(261)
#110: 528 = g(264)
#111: 529 = h(132)
#112: 530 = g(265)
#113: 532 = g(266)
#114: 533 = h(133)
#115: 544 = g(272)
#116: 545 = h(136)
#117: 546 = g(273)
#118: 548 = g(274)
#119: 549 = h(137)
#120: 552 = g(276)
#121: 553 = h(138)
#122: 554 = g(277)
#123: 576 = g(288)
#124: 577 = h(144)
#125: 578 = g(289)
#126: 580 = g(290)
#127: 581 = h(145)
#128: 584 = g(292)
#129: 585 = h(146)
#130: 586 = g(293)
#131: 592 = g(296)
#132: 593 = h(148)
#133: 594 = g(297)
#134: 596 = g(298)
#135: 597 = h(149)
#136: 625 = f(25)
#137: 640 = g(320)
#138: 641 = h(160)
#139: 642 = g(321)
#140: 644 = g(322)
#141: 645 = h(161)
#142: 648 = g(324)
#143: 649 = h(162)
#144: 650 = g(325)
#145: 656 = g(328)
#146: 657 = h(164)
#147: 658 = g(329)
#148: 660 = g(330)
#149: 661 = h(165)
#150: 672 = g(336)
#151: 673 = h(168)
#152: 674 = g(337)
#153: 676 = g(338)
#154: 677 = h(169)
#155: 680 = g(340)
#156: 681 = h(170)
#157: 682 = g(341)
#158: 800 = g(400)
#159: 801 = h(200)
#160: 802 = g(401)
#161: 804 = g(402)
#162: 805 = h(201)
#163: 808 = g(404)
#164: 809 = h(202)
#165: 810 = g(405)
#166: 882 = g(441)
#167: 1024 = g(512)
#168: 1025 = h(256)
#169: 1026 = g(513)
#170: 1028 = g(514)
#171: 1029 = h(257)
#172: 1032 = g(516)
#173: 1033 = h(258)
#174: 1034 = g(517)
#175: 1040 = g(520)
#176: 1041 = h(260)
#177: 1042 = g(521)
#178: 1044 = g(522)
#179: 1045 = h(261)
#180: 1056 = g(528)
#181: 1057 = h(264)
#182: 1058 = g(529)
#183: 1060 = g(530)
#184: 1061 = h(265)
#185: 1064 = g(532)
#186: 1065 = h(266)
#187: 1066 = g(533)
#188: 1088 = g(544)
#189: 1089 = h(272)
#190: 1090 = g(545)
#191: 1092 = g(546)
#192: 1093 = h(273)
#193: 1096 = g(548)
#194: 1097 = h(274)
#195: 1098 = g(549)
#196: 1104 = g(552)
#197: 1105 = h(276)
#198: 1106 = g(553)
#199: 1108 = g(554)
#200: 1109 = h(277)
#201: 1152 = g(576)
#202: 1153 = h(288)
#203: 1154 = g(577)
#204: 1156 = g(578)
#205: 1157 = h(289)
#206: 1160 = g(580)
#207: 1161 = h(290)
#208: 1162 = g(581)
#209: 1168 = g(584)
#210: 1169 = h(292)
#211: 1170 = g(585)
#212: 1172 = g(586)
#213: 1173 = h(293)
#214: 1184 = g(592)
#215: 1185 = h(296)
#216: 1186 = g(593)
#217: 1188 = g(594)
#218: 1189 = h(297)
#219: 1192 = g(596)
#220: 1193 = h(298)
#221: 1194 = g(597)
#222: 1250 = g(625)
#223: 1280 = g(640)
#224: 1281 = h(320)
#225: 1282 = g(641)
#226: 1284 = g(642)
#227: 1285 = h(321)
#228: 1288 = g(644)
#229: 1289 = h(322)
#230: 1290 = g(645)
#231: 1296 = g(648)
#232: 1297 = h(324)
#233: 1298 = g(649)
#234: 1300 = g(650)
#235: 1301 = h(325)
#236: 1312 = g(656)
#237: 1313 = h(328)
#238: 1314 = g(657)
#239: 1316 = g(658)
#240: 1317 = h(329)
#241: 1320 = g(660)
#242: 1321 = h(330)
#243: 1322 = g(661)
#244: 1344 = g(672)
#245: 1345 = h(336)
#246: 1346 = g(673)
#247: 1348 = g(674)
#248: 1349 = h(337)
#249: 1352 = g(676)
#250: 1353 = h(338)
#251: 1354 = g(677)
#252: 1360 = g(680)
#253: 1361 = h(340)
#254: 1362 = g(681)
#255: 1364 = g(682)
#256: 1365 = h(341)
#257: 1369 = f(37)
#258: 1600 = g(800)
#259: 1601 = h(400)
#260: 1602 = g(801)
#261: 1604 = g(802)
#262: 1605 = h(401)
#263: 1608 = g(804)
#264: 1609 = h(402)
#265: 1610 = g(805)
#266: 1616 = g(808)
#267: 1617 = h(404)
#268: 1618 = g(809)
#269: 1620 = g(810)
#270: 1621 = h(405)
#271: 1681 = f(41)
#272: 1764 = g(882)
#273: 1765 = h(441)
#274: 2048 = g(1024)

C code to identify and count the numbers:

#include <stdio.h>
int main()
{
int S;
int n,t;
for(n=0;n<2049;++n)S[n]=0; // initialize
S=1; // mark h(0) = 1 in S
for(n=t=0;n<2049;++n){
if(S[n]){ // if n is in S
++t;
if(n<46) S[n*n]=1; // mark f(n) in S
if(n<1025) S[n+n]=1; // mark g(n) in S
if(n<512) S[4*n+1]=1; // mark h(n) in S
}
}
printf("%d",t);
return 0;
}


Computerless solution

There are

274 numbers

in the set S.

Let's first of all consider

just the functions g,h, which append 0 and 01 respectively to the binary representation of their arguments. By starting with 0 and iterating these we can get any number whose binary representation has no two consecutive 1s. These aren't too painful to enumerate by hand: once we've found all of them below each power of 2 up to 2^n, we get the next block by adding 2^n to all the ones below 2^(n-1). But we don't actually need to enumerate them, we just need (1) to know how many there are and (2) to be able to recognize them. For (1), it's not hard to see that the number of these below 2^n is F(n+2), the (n+2)'th Fibonacci number. For (2), we can just look at the binary representation of any number we're curious about. So, we have F_13 = 233 of these below 2048, and hence 234 of them up to 2048 inclusive.

Well, actually

we do need to enumerate the first few -- as we'll see in the next paragraph, we need the ones up to 45. So, in blocks corresponding to powers of 2 as described above:
0 | 1 | 2 | 4 5 | 8 9 10 | 16 17 18 20 21 | 32 33 34 36 37 40 41 42 | 64 ...

Anyway, we aren't done yet, because

some squares of these numbers might not be of the required form. To be < 2048 they'd need to be squares of numbers <= 45, so let's square the first few numbers in the list above:
0 1 4 16 25 64 81 100 256 289 324 400 441 1024 1089 1156 1296 1369 1600 1681 1764.

We now have

8 new numbers, for a total of 242 so far.

Now we need to augment our list by

appending "0"s and "01"s to these, with a limit of 2048 as usual. None of the numbers this yields can be in our list of 234 numbers because they all have two adjacent 1s.
From 25 we get 50, (100), 101, 200, 201, 202,
(400), 401, 402, 404, 405, 800, 801, 802, 804, 805, 808, 809, 810,
(1600), 1601, 1602, 1604, 1605, 1608, 1609, 1610, 1616, 1617, 1618, 1620, 1621.
That's 29 new numbers, taking us to 271.
From 100 and 400 we get only things we already got from 25.
From 441 we get 882, (1764), 1765: 2 new numbers, taking us to 273.
The next new square is 1369, and anything obtained from that is > 2048.

We're still not quite done because we need to consider

squaring our new numbers. That gets us 625 (which, having adjacent 1s in its binary representation and not being one of the numbers we've just written down, is new), and hence also 1250. Now we're on 275,

and now we're done, except that I have included the 0 with which we start and the question asks about positive integers, so the required answer is actually 1 less.

• Zero is not in S Nov 16 at 23:43
• Yeah, you're right. (As it happens I'd just spotted that myself, on comparing my answer with yours which is almost the same but produces a value off by one.) I was fooled by the "starting with 0" in the process :-). [EDITED to add:] Fixed now. Nov 16 at 23:45
• As it happens, I just completed the manual solution myself, and was about to edit my answer... :o( Nov 16 at 23:46
• Oh no! I'm sorry. But not very sorry. :-) Nov 16 at 23:46
• @GarethMcCaughan Good job on the first computerless solution! :D Guess I wasn't expecting an answer from math themself! Nov 16 at 23:49

Computer Assisted Solution:

There are 229 numbers in $$\mathbb S$$

Algorithm:

4 Columns in Excel n, F(n), G(n), H(n).
n goes from 1-2048, the rest are calculated.
So, the first row, is everything you can calculate with n=1 (1, 2, 5)
This means 2 is a valid row, and yields (4,4,9).
For any row to be valid, its n value MUST exist as a result in the previous rows. If it doesn't, it can't be calculated.
Row 3 can be deleted, as 3 does not exist as a previous result.
You can do this manually, or add a few extra columns and use some clever lookup() and find() functions and set a flag indicating if a row is valid or not.

• good job!! Don't worry, that's the correct answer! :) although I really doubt it's solvable normally without it taking an extremely long amount of time tbh Nov 16 at 20:11