Counting puzzle #1: Function combinations

Question

_{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.}

Answer 1

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[2049];
  int n,t;
  for(n=0;n<2049;++n)S[n]=0; // initialize
  S[1]=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;
}

Answer 2

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.

Answer 3

Computer Assisted Solution:

Answer:

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.