Counting Zeros

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
measure
Posts: 129
Joined: Sat Apr 04, 2015 4:31 pm UTC
Location: Time-traveling kayak

Counting Zeros

Postby measure » Fri Aug 05, 2016 10:22 pm UTC

Consider the sequence 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4... (https://oeis.org/A007814).
The value at every odd position is zero. The value at every even position is one more than the value at half of that position.
The value at general position n can be found by counting the trailing zeros of the binary representation of n.
Call this function f2(n).

Define f3(n) similarly as the number of trailing zeros in the base-3 representation of n (https://oeis.org/A007949).

Finally, define s(n) as the sum of all f(n). That is, the sum over all b of the number of trailing zeros in the representation of n in base-b.
For example, s(4)=3 since f2(4)=2, f3(4)=0, f4(4)=1, and for b>4, f(4)=0, so 2+0+1=3.

I wrote a script to calculate values of s(n) up to n=3000:

Code: Select all

1   0
2   1
3   1
4   3
5   1
6   3
7   1
8   5
9   3
10   3
11   1
12   6
13   1
14   3
15   3
16   8
17   1
18   6
19   1
20   6
21   3
22   3
23   1
24   9
25   3
26   3
27   5
28   6
29   1
30   7
31   1
32   10
33   3
34   3
35   3
36   11
37   1
38   3
39   3
40   9
41   1
42   7
43   1
44   6
45   6
46   3
47   1
48   13
49   3
50   6
51   3
52   6
53   1
54   9
55   3
56   9
57   3
58   3
59   1
60   12
61   1
62   3
63   6
64   14
65   3
66   7
67   1
68   6
69   3
70   7
71   1
72   15
73   1
74   3
75   6
76   6
77   3
78   7
79   1
80   13
81   8
82   3
83   1
84   12
85   3
86   3
87   3
88   9
89   1
90   12
91   3
92   6
93   3
94   3
95   3
96   16
97   1
98   6
99   6
100   11
101   1
102   7
103   1
104   9
105   7
106   3
107   1
108   15
109   1
110   7
111   3
112   13
113   1
114   7
115   3
116   6
117   6
118   3
119   3
120   17
121   3
122   3
123   3
124   6
125   5
126   12
127   1
128   16
129   3
130   7
131   1
132   12
133   3
134   3
135   9
136   9
137   1
138   7
139   1
140   12
141   3
142   3
143   3
144   21
145   3
146   3
147   6
148   6
149   1
150   12
151   1
152   9
153   6
154   7
155   3
156   12
157   1
158   3
159   3
160   16
161   3
162   13
163   1
164   6
165   7
166   3
167   1
168   17
169   3
170   7
171   6
172   6
173   1
174   7
175   6
176   13
177   3
178   3
179   1
180   20
181   1
182   7
183   3
184   9
185   3
186   7
187   3
188   6
189   9
190   7
191   1
192   21
193   1
194   3
195   7
196   11
197   1
198   12
199   1
200   15
201   3
202   3
203   3
204   12
205   3
206   3
207   6
208   13
209   3
210   15
211   1
212   6
213   3
214   3
215   3
216   21
217   3
218   3
219   3
220   12
221   3
222   7
223   1
224   16
225   11
226   3
227   1
228   12
229   1
230   7
231   7
232   9
233   1
234   12
235   3
236   6
237   3
238   7
239   1
240   23
241   1
242   6
243   10
244   6
245   6
246   7
247   3
248   9
249   3
250   9
251   1
252   20
253   3
254   3
255   7
256   20
257   1
258   7
259   3
260   12
261   6
262   3
263   1
264   17
265   3
266   7
267   3
268   6
269   1
270   17
271   1
272   13
273   7
274   3
275   6
276   12
277   1
278   3
279   6
280   17
281   1
282   7
283   1
284   6
285   7
286   7
287   3
288   25
289   3
290   7
291   3
292   6
293   1
294   12
295   3
296   9
297   9
298   3
299   3
300   20
301   3
302   3
303   3
304   13
305   3
306   12
307   1
308   12
309   3
310   7
311   1
312   17
313   1
314   3
315   12
316   6
317   1
318   7
319   3
320   21
321   3
322   7
323   3
324   21
325   6
326   3
327   3
328   9
329   3
330   15
331   1
332   6
333   6
334   3
335   3
336   23
337   1
338   6
339   3
340   12
341   3
342   12
343   5
344   9
345   7
346   3
347   1
348   12
349   1
350   12
351   9
352   16
353   1
354   7
355   3
356   6
357   7
358   3
359   1
360   27
361   3
362   3
363   6
364   12
365   3
366   7
367   1
368   13
369   6
370   7
371   3
372   12
373   1
374   7
375   9
376   9
377   3
378   17
379   1
380   12
381   3
382   3
383   1
384   24
385   7
386   3
387   6
388   6
389   1
390   15
391   3
392   15
393   3
394   3
395   3
396   20
397   1
398   3
399   7
400   21
401   1
402   7
403   3
404   6
405   13
406   7
407   3
408   17
409   1
410   7
411   3
412   6
413   3
414   12
415   3
416   16
417   3
418   7
419   1
420   24
421   1
422   3
423   6
424   9
425   6
426   7
427   3
428   6
429   7
430   7
431   1
432   28
433   1
434   7
435   7
436   6
437   3
438   7
439   1
440   17
441   11
442   7
443   1
444   12
445   3
446   3
447   3
448   21
449   1
450   20
451   3
452   6
453   3
454   3
455   7
456   17
457   1
458   3
459   9
460   12
461   1
462   15
463   1
464   13
465   7
466   3
467   1
468   20
469   3
470   7
471   3
472   9
473   3
474   7
475   6
476   12
477   6
478   3
479   1
480   28
481   3
482   3
483   7
484   11
485   3
486   16
487   1
488   9
489   3
490   12
491   1
492   12
493   3
494   7
495   12
496   13
497   3
498   7
499   1
500   15
501   3
502   3
503   1
504   27
505   3
506   7
507   6
508   6
509   1
510   15
511   3
512   23
513   9
514   3
515   3
516   12
517   3
518   7
519   3
520   17
521   1
522   12
523   1
524   6
525   12
526   3
527   3
528   23
529   3
530   7
531   6
532   12
533   3
534   7
535   3
536   9
537   3
538   3
539   6
540   27
541   1
542   3
543   3
544   16
545   3
546   15
547   1
548   6
549   6
550   12
551   3
552   17
553   3
554   3
555   7
556   6
557   1
558   12
559   3
560   23
561   7
562   3
563   1
564   12
565   3
566   3
567   13
568   9
569   1
570   15
571   1
572   12
573   3
574   7
575   6
576   32
577   1
578   6
579   3
580   12
581   3
582   7
583   3
584   9
585   12
586   3
587   1
588   20
589   3
590   7
591   3
592   13
593   1
594   17
595   7
596   6
597   3
598   7
599   1
600   27
601   1
602   7
603   6
604   6
605   6
606   7
607   1
608   16
609   7
610   7
611   3
612   20
613   1
614   3
615   7
616   17
617   1
618   7
619   1
620   12
621   9
622   3
623   3
624   23
625   8
626   3
627   7
628   6
629   3
630   24
631   1
632   9
633   3
634   3
635   3
636   12
637   6
638   7
639   6
640   24
641   1
642   7
643   1
644   12
645   7
646   7
647   1
648   28
649   3
650   12
651   7
652   6
653   1
654   7
655   3
656   13
657   6
658   7
659   1
660   24
661   1
662   3
663   7
664   9
665   7
666   12
667   3
668   6
669   3
670   7
671   3
672   28
673   1
674   3
675   15
676   11
677   1
678   7
679   3
680   17
681   3
682   7
683   1
684   20
685   3
686   9
687   3
688   13
689   3
690   15
691   1
692   6
693   12
694   3
695   3
696   17
697   3
698   3
699   3
700   20
701   1
702   17
703   3
704   21
705   7
706   3
707   3
708   12
709   1
710   7
711   6
712   9
713   3
714   15
715   7
716   6
717   3
718   3
719   1
720   36
721   3
722   6
723   3
724   6
725   6
726   12
727   1
728   17
729   14
730   7
731   3
732   12
733   1
734   3
735   12
736   16
737   3
738   12
739   1
740   12
741   7
742   7
743   1
744   17
745   3
746   3
747   6
748   12
749   3
750   17
751   1
752   13
753   3
754   7
755   3
756   27
757   1
758   3
759   7
760   17
761   1
762   7
763   3
764   6
765   12
766   3
767   3
768   29
769   1
770   15
771   3
772   6
773   1
774   12
775   6
776   9
777   7
778   3
779   3
780   24
781   3
782   7
783   9
784   21
785   3
786   7
787   1
788   6
789   3
790   7
791   3
792   27
793   3
794   3
795   7
796   6
797   1
798   15
799   3
800   25
801   6
802   3
803   3
804   12
805   7
806   7
807   3
808   9
809   1
810   23
811   1
812   12
813   3
814   7
815   3
816   23
817   3
818   3
819   12
820   12
821   1
822   7
823   1
824   9
825   12
826   7
827   1
828   20
829   1
830   7
831   3
832   21
833   6
834   7
835   3
836   12
837   9
838   3
839   1
840   33
841   3
842   3
843   3
844   6
845   6
846   12
847   6
848   13
849   3
850   12
851   3
852   12
853   1
854   7
855   12
856   9
857   1
858   15
859   1
860   12
861   7
862   3
863   1
864   33
865   3
866   3
867   6
868   12
869   3
870   15
871   3
872   9
873   6
874   7
875   9
876   12
877   1
878   3
879   3
880   23
881   1
882   20
883   1
884   12
885   7
886   3
887   1
888   17
889   3
890   7
891   13
892   6
893   3
894   7
895   3
896   24
897   7
898   3
899   3
900   33
901   3
902   7
903   7
904   9
905   3
906   7
907   1
908   6
909   6
910   15
911   1
912   23
913   3
914   3
915   7
916   6
917   3
918   17
919   1
920   17
921   3
922   3
923   3
924   24
925   6
926   3
927   6
928   16
929   1
930   15
931   6
932   6
933   3
934   3
935   7
936   27
937   1
938   7
939   3
940   12
941   1
942   7
943   3
944   13
945   17
946   7
947   1
948   12
949   3
950   12
951   3
952   17
953   1
954   12
955   3
956   6
957   7
958   3
959   3
960   35
961   3
962   7
963   6
964   6
965   3
966   15
967   1
968   15
969   7
970   7
971   1
972   25
973   3
974   3
975   12
976   13
977   1
978   7
979   3
980   20
981   6
982   3
983   1
984   17
985   3
986   7
987   7
988   12
989   3
990   24
991   1
992   16
993   3
994   7
995   3
996   12
997   1
998   3
999   9
1000   21
1001   7
1002   7
1003   3
1004   6
1005   7
1006   3
1007   3
1008   36
1009   1
1010   7
1011   3
1012   12
1013   1
1014   12
1015   7
1016   9
1017   6
1018   3
1019   1
1020   24
1021   1
1022   7
1023   7
1024   27
1025   6
1026   17
1027   3
1028   6
1029   9
1030   7
1031   1
1032   17
1033   1
1034   7
1035   12
1036   12
1037   3
1038   7
1039   1
1040   23
1041   3
1042   3
1043   3
1044   20
1045   7
1046   3
1047   3
1048   9
1049   1
1050   24
1051   1
1052   6
1053   13
1054   7
1055   3
1056   28
1057   3
1058   6
1059   3
1060   12
1061   1
1062   12
1063   1
1064   17
1065   7
1066   7
1067   3
1068   12
1069   1
1070   7
1071   12
1072   13
1073   3
1074   7
1075   6
1076   6
1077   3
1078   12
1079   3
1080   37
1081   3
1082   3
1083   6
1084   6
1085   7
1086   7
1087   1
1088   21
1089   11
1090   7
1091   1
1092   24
1093   1
1094   3
1095   7
1096   9
1097   1
1098   12
1099   3
1100   20
1101   3
1102   7
1103   1
1104   23
1105   7
1106   7
1107   9
1108   6
1109   1
1110   15
1111   3
1112   9
1113   7
1114   3
1115   3
1116   20
1117   1
1118   7
1119   3
1120   28
1121   3
1122   15
1123   1
1124   6
1125   15
1126   3
1127   6
1128   17
1129   1
1130   7
1131   7
1132   6
1133   3
1134   23
1135   3
1136   13
1137   3
1138   3
1139   3
1140   24
1141   3
1142   3
1143   6
1144   17
1145   3
1146   7
1147   3
1148   12
1149   3
1150   12
1151   1
1152   36
1153   1
1154   3
1155   15
1156   11
1157   3
1158   7
1159   3
1160   17
1161   9
1162   7
1163   1
1164   12
1165   3
1166   7
1167   3
1168   13
1169   3
1170   24
1171   1
1172   6
1173   7
1174   3
1175   6
1176   27
1177   3
1178   7
1179   6
1180   12
1181   1
1182   7
1183   6
1184   16
1185   7
1186   3
1187   1
1188   27
1189   3
1190   15
1191   3
1192   9
1193   1
1194   7
1195   3
1196   12
1197   12
1198   3
1199   3
1200   36
1201   1
1202   3
1203   3
1204   12
1205   3
1206   12
1207   3
1208   9
1209   7
1210   12
1211   3
1212   12
1213   1
1214   3
1215   16
1216   21
1217   1
1218   15
1219   3
1220   12
1221   7
1222   7
1223   1
1224   27
1225   11
1226   3
1227   3
1228   6
1229   1
1230   15
1231   1
1232   23
1233   6
1234   3
1235   7
1236   12
1237   1
1238   3
1239   7
1240   17
1241   3
1242   17
1243   3
1244   6
1245   7
1246   7
1247   3
1248   28
1249   1
1250   13
1251   6
1252   6
1253   3
1254   15
1255   3
1256   9
1257   3
1258   7
1259   1
1260   38
1261   3
1262   3
1263   3
1264   13
1265   7
1266   7
1267   3
1268   6
1269   9
1270   7
1271   3
1272   17
1273   3
1274   12
1275   12
1276   12
1277   1
1278   12
1279   1
1280   29
1281   7
1282   3
1283   1
1284   12
1285   3
1286   3
1287   12
1288   17
1289   1
1290   15
1291   1
1292   12
1293   3
1294   3
1295   7
1296   38
1297   1
1298   7
1299   3
1300   20
1301   1
1302   15
1303   1
1304   9
1305   12
1306   3
1307   1
1308   12
1309   7
1310   7
1311   7
1312   16
1313   3
1314   12
1315   3
1316   12
1317   3
1318   3
1319   1
1320   33
1321   1
1322   3
1323   15
1324   6
1325   6
1326   15
1327   1
1328   13
1329   3
1330   15
1331   5
1332   20
1333   3
1334   7
1335   7
1336   9
1337   3
1338   7
1339   3
1340   12
1341   6
1342   7
1343   3
1344   35
1345   3
1346   3
1347   3
1348   6
1349   3
1350   27
1351   3
1352   15
1353   7
1354   3
1355   3
1356   12
1357   3
1358   7
1359   6
1360   23
1361   1
1362   7
1363   3
1364   12
1365   15
1366   3
1367   1
1368   27
1369   3
1370   7
1371   3
1372   15
1373   1
1374   7
1375   9
1376   16
1377   13
1378   7
1379   3
1380   24
1381   1
1382   3
1383   3
1384   9
1385   3
1386   24
1387   3
1388   6
1389   3
1390   7
1391   3
1392   23
1393   3
1394   7
1395   12
1396   6
1397   3
1398   7
1399   1
1400   27
1401   3
1402   3
1403   3
1404   27
1405   3
1406   7
1407   7
1408   24
1409   1
1410   15
1411   3
1412   6
1413   6
1414   7
1415   3
1416   17
1417   3
1418   3
1419   7
1420   12
1421   6
1422   12
1423   1
1424   13
1425   12
1426   7
1427   1
1428   24
1429   1
1430   15
1431   9
1432   9
1433   1
1434   7
1435   7
1436   6
1437   3
1438   3
1439   1
1440   43
1441   3
1442   7
1443   7
1444   11
1445   6
1446   7
1447   1
1448   9
1449   12
1450   12
1451   1
1452   20
1453   1
1454   3
1455   7
1456   23
1457   3
1458   21
1459   1
1460   12
1461   3
1462   7
1463   7
1464   17
1465   3
1466   3
1467   6
1468   6
1469   3
1470   24
1471   1
1472   21
1473   3
1474   7
1475   6
1476   20
1477   3
1478   3
1479   7
1480   17
1481   1
1482   15
1483   1
1484   12
1485   17
1486   3
1487   1
1488   23
1489   1
1490   7
1491   7
1492   6
1493   1
1494   12
1495   7
1496   17
1497   3
1498   7
1499   1
1500   27
1501   3
1502   3
1503   6
1504   16
1505   7
1506   7
1507   3
1508   12
1509   3
1510   7
1511   1
1512   37
1513   3
1514   3
1515   7
1516   6
1517   3
1518   15
1519   6
1520   23
1521   11
1522   3
1523   1
1524   12
1525   6
1526   7
1527   3
1528   9
1529   3
1530   24
1531   1
1532   6
1533   7
1534   7
1535   3
1536   33
1537   3
1538   3
1539   13
1540   24
1541   3
1542   7
1543   1
1544   9
1545   7
1546   3
1547   7
1548   20
1549   1
1550   12
1551   7
1552   13
1553   1
1554   15
1555   3
1556   6
1557   6
1558   7
1559   1
1560   33
1561   3
1562   7
1563   3
1564   12
1565   3
1566   17
1567   1
1568   25
1569   3
1570   7
1571   1
1572   12
1573   6
1574   3
1575   20
1576   9
1577   3
1578   7
1579   1
1580   12
1581   7
1582   7
1583   1
1584   36
1585   3
1586   7
1587   6
1588   6
1589   3
1590   15
1591   3
1592   9
1593   9
1594   3
1595   7
1596   24
1597   1
1598   7
1599   7
1600   32
1601   1
1602   12
1603   3
1604   6
1605   7
1606   7
1607   1
1608   17
1609   1
1610   15
1611   6
1612   12
1613   1
1614   7
1615   7
1616   13
1617   12
1618   3
1619   1
1620   36
1621   1
1622   3
1623   3
1624   17
1625   9
1626   7
1627   1
1628   12
1629   6
1630   7
1631   3
1632   28
1633   3
1634   7
1635   7
1636   6
1637   1
1638   24
1639   3
1640   17
1641   3
1642   3
1643   3
1644   12
1645   7
1646   3
1647   9
1648   13
1649   3
1650   24
1651   3
1652   12
1653   7
1654   3
1655   3
1656   27
1657   1
1658   3
1659   7
1660   12
1661   3
1662   7
1663   1
1664   24
1665   12
1666   12
1667   1
1668   12
1669   1
1670   7
1671   3
1672   17
1673   3
1674   17
1675   6
1676   6
1677   7
1678   3
1679   3
1680   43
1681   3
1682   6
1683   12
1684   6
1685   3
1686   7
1687   3
1688   9
1689   3
1690   12
1691   3
1692   20
1693   1
1694   12
1695   7
1696   16
1697   1
1698   7
1699   1
1700   20
1701   16
1702   7
1703   3
1704   17
1705   7
1706   3
1707   3
1708   12
1709   1
1710   24
1711   3
1712   13
1713   3
1714   3
1715   9
1716   24
1717   3
1718   3
1719   6
1720   17
1721   1
1722   15
1723   1
1724   6
1725   12
1726   3
1727   3
1728   42
1729   7
1730   7
1731   3
1732   6
1733   1
1734   12
1735   3
1736   17
1737   6
1738   7
1739   3
1740   24
1741   1
1742   7
1743   7
1744   13
1745   3
1746   12
1747   1
1748   12
1749   7
1750   17
1751   3
1752   17
1753   1
1754   3
1755   17
1756   6
1757   3
1758   7
1759   1
1760   28
1761   3
1762   3
1763   3
1764   33
1765   3
1766   3
1767   7
1768   17
1769   3
1770   15
1771   7
1772   6
1773   6
1774   3
1775   6
1776   23
1777   1
1778   7
1779   3
1780   12
1781   3
1782   23
1783   1
1784   9
1785   15
1786   7
1787   1
1788   12
1789   1
1790   7
1791   6
1792   29
1793   3
1794   15
1795   3
1796   6
1797   3
1798   7
1799   3
1800   43
1801   1
1802   7
1803   3
1804   12
1805   6
1806   15
1807   3
1808   13
1809   9
1810   7
1811   1
1812   12
1813   6
1814   3
1815   12
1816   9
1817   3
1818   12
1819   3
1820   24
1821   3
1822   3
1823   1
1824   28
1825   6
1826   7
1827   12
1828   6
1829   3
1830   15
1831   1
1832   9
1833   7
1834   7
1835   3
1836   27
1837   3
1838   3
1839   3
1840   23
1841   3
1842   7
1843   3
1844   6
1845   12
1846   7
1847   1
1848   33
1849   3
1850   12
1851   3
1852   6
1853   3
1854   12
1855   7
1856   21
1857   3
1858   3
1859   6
1860   24
1861   1
1862   12
1863   13
1864   9
1865   3
1866   7
1867   1
1868   6
1869   7
1870   15
1871   1
1872   36
1873   1
1874   3
1875   13
1876   12
1877   1
1878   7
1879   1
1880   17
1881   12
1882   3
1883   3
1884   12
1885   7
1886   7
1887   7
1888   16
1889   1
1890   33
1891   3
1892   12
1893   3
1894   3
1895   3
1896   17
1897   3
1898   7
1899   6
1900   20
1901   1
1902   7
1903   3
1904   23
1905   7
1906   3
1907   1
1908   20
1909   3
1910   7
1911   12
1912   9
1913   1
1914   15
1915   3
1916   6
1917   9
1918   7
1919   3
1920   40
1921   3
1922   6
1923   3
1924   12
1925   12
1926   12
1927   3
1928   9
1929   3
1930   7
1931   1
1932   24
1933   1
1934   3
1935   12
1936   21
1937   3
1938   15
1939   3
1940   12
1941   3
1942   3
1943   3
1944   33
1945   3
1946   7
1947   7
1948   6
1949   1
1950   24
1951   1
1952   16
1953   12
1954   3
1955   7
1956   12
1957   3
1958   7
1959   3
1960   27
1961   3
1962   12
1963   3
1964   6
1965   7
1966   3
1967   3
1968   23
1969   3
1970   7
1971   9
1972   12
1973   1
1974   15
1975   6
1976   17
1977   3
1978   7
1979   1
1980   38
1981   3
1982   3
1983   3
1984   21
1985   3
1986   7
1987   1
1988   12
1989   12
1990   7
1991   3
1992   17
1993   1
1994   3
1995   15
1996   6
1997   1
1998   17
1999   1
2000   28
2001   7
2002   15
2003   1
2004   12
2005   3
2006   7
2007   6
2008   9
2009   6
2010   15
2011   1
2012   6
2013   7
2014   7
2015   7
2016   43
2017   1
2018   3
2019   3
2020   12
2021   3
2022   7
2023   6
2024   17
2025   21
2026   3
2027   1
2028   20
2029   1
2030   15
2031   3
2032   13
2033   3
2034   12
2035   7
2036   6
2037   7
2038   3
2039   1
2040   33
2041   3
2042   3
2043   6
2044   12
2045   3
2046   15
2047   3
2048   29
2049   3
2050   12
2051   3
2052   27
2053   1
2054   7
2055   7
2056   9
2057   6
2058   17
2059   3
2060   12
2061   6
2062   3
2063   1
2064   23
2065   7
2066   3
2067   7
2068   12
2069   1
2070   24
2071   3
2072   17
2073   3
2074   7
2075   6
2076   12
2077   3
2078   3
2079   17
2080   28
2081   1
2082   7
2083   1
2084   6
2085   7
2086   7
2087   1
2088   27
2089   1
2090   15
2091   7
2092   6
2093   7
2094   7
2095   3
2096   13
2097   6
2098   3
2099   1
2100   38
2101   3
2102   3
2103   3
2104   9
2105   3
2106   23
2107   6
2108   12
2109   7
2110   7
2111   1
2112   35
2113   1
2114   7
2115   12
2116   11
2117   3
2118   7
2119   3
2120   17
2121   7
2122   3
2123   3
2124   20
2125   9
2126   3
2127   3
2128   23
2129   1
2130   15
2131   1
2132   12
2133   9
2134   7
2135   7
2136   17
2137   1
2138   3
2139   7
2140   12
2141   1
2142   24
2143   1
2144   16
2145   15
2146   7
2147   3
2148   12
2149   3
2150   12
2151   6
2152   9
2153   1
2154   7
2155   3
2156   20
2157   3
2158   7
2159   3
2160   48
2161   1
2162   7
2163   7
2164   6
2165   3
2166   12
2167   3
2168   9
2169   6
2170   15
2171   3
2172   12
2173   3
2174   3
2175   12
2176   24
2177   3
2178   20
2179   1
2180   12
2181   3
2182   3
2183   3
2184   33
2185   7
2186   3
2187   16
2188   6
2189   3
2190   15
2191   3
2192   13
2193   7
2194   3
2195   3
2196   20
2197   5
2198   7
2199   3
2200   27
2201   3
2202   7
2203   1
2204   12
2205   20
2206   3
2207   1
2208   28
2209   3
2210   15
2211   7
2212   12
2213   1
2214   17
2215   3
2216   9
2217   3
2218   3
2219   3
2220   24
2221   1
2222   7
2223   12
2224   13
2225   6
2226   15
2227   3
2228   6
2229   3
2230   7
2231   3
2232   27
2233   7
2234   3
2235   7
2236   12
2237   1
2238   7
2239   1
2240   35
2241   9
2242   7
2243   1
2244   24
2245   3
2246   3
2247   7
2248   9
2249   3
2250   27
2251   1
2252   6
2253   3
2254   12
2255   7
2256   23
2257   3
2258   3
2259   6
2260   12
2261   7
2262   15
2263   3
2264   9
2265   7
2266   7
2267   1
2268   36
2269   1
2270   7
2271   3
2272   16
2273   1
2274   7
2275   12
2276   6
2277   12
2278   7
2279   3
2280   33
2281   1
2282   7
2283   3
2284   6
2285   3
2286   12
2287   1
2288   23
2289   7
2290   7
2291   3
2292   12
2293   1
2294   7
2295   17
2296   17
2297   1
2298   7
2299   6
2300   20
2301   7
2302   3
2303   6
2304   43
2305   3
2306   3
2307   3
2308   6
2309   1
2310   31
2311   1
2312   15
2313   6
2314   7
2315   3
2316   12
2317   3
2318   7
2319   3
2320   23
2321   3
2322   17
2323   3
2324   12
2325   12
2326   3
2327   3
2328   17
2329   3
2330   7
2331   12
2332   12
2333   1
2334   7
2335   3
2336   16
2337   7
2338   7
2339   1
2340   38
2341   1
2342   3
2343   7
2344   9
2345   7
2346   15
2347   1
2348   6
2349   13
2350   12
2351   1
2352   36
2353   3
2354   7
2355   7
2356   12
2357   1
2358   12
2359   3
2360   17
2361   3
2362   3
2363   3
2364   12
2365   7
2366   12
2367   6
2368   21
2369   3
2370   15
2371   1
2372   6
2373   7
2374   3
2375   9
2376   37
2377   1
2378   7
2379   7
2380   24
2381   1
2382   7
2383   1
2384   13
2385   12
2386   3
2387   7
2388   12
2389   1
2390   7
2391   3
2392   17
2393   1
2394   24
2395   3
2396   6
2397   7
2398   7
2399   1
2400   43
2401   8
2402   3
2403   9
2404   6
2405   7
2406   7
2407   3
2408   17
2409   7
2410   7
2411   1
2412   20
2413   3
2414   7
2415   15
2416   13
2417   1
2418   15
2419   3
2420   20
2421   6
2422   7
2423   1
2424   17
2425   6
2426   3
2427   3
2428   6
2429   3
2430   28
2431   7
2432   24
2433   3
2434   3
2435   3
2436   24
2437   1
2438   7
2439   6
2440   17
2441   1
2442   15
2443   3
2444   12
2445   7
2446   3
2447   1
2448   36
2449   3
2450   20
2451   7
2452   6
2453   3
2454   7
2455   3
2456   9
2457   17
2458   3
2459   1
2460   24
2461   3
2462   3
2463   3
2464   28
2465   7
2466   12
2467   1
2468   6
2469   3
2470   15
2471   3
2472   17
2473   1
2474   3
2475   20
2476   6
2477   1
2478   15
2479   3
2480   23
2481   3
2482   7
2483   3
2484   27
2485   7
2486   7
2487   3
2488   9
2489   3
2490   15
2491   3
2492   12
2493   6
2494   7
2495   3
2496   35
2497   3
2498   3
2499   12
2500   21
2501   3
2502   12
2503   1
2504   9
2505   7
2506   7
2507   3
2508   24
2509   3
2510   7
2511   13
2512   13
2513   3
2514   7
2515   3
2516   12
2517   3
2518   3
2519   3
2520   51
2521   1
2522   7
2523   6
2524   6
2525   6
2526   7
2527   6
2528   16
2529   6
2530   15
2531   1
2532   12
2533   3
2534   7
2535   12
2536   9
2537   3
2538   17
2539   1
2540   12
2541   12
2542   7
2543   1
2544   23
2545   3
2546   7
2547   6
2548   20
2549   1
2550   24
2551   1
2552   17
2553   7
2554   3
2555   7
2556   20
2557   1
2558   3
2559   3
2560   33
2561   3
2562   15
2563   3
2564   6
2565   17
2566   3
2567   3
2568   17
2569   3
2570   7
2571   3
2572   6
2573   3
2574   24
2575   6
2576   23
2577   3
2578   3
2579   1
2580   24
2581   3
2582   3
2583   12
2584   17
2585   7
2586   7
2587   3
2588   6
2589   3
2590   15
2591   1
2592   44
2593   1
2594   3
2595   7
2596   12
2597   6
2598   7
2599   3
2600   27
2601   11
2602   3
2603   3
2604   24
2605   3
2606   3
2607   7
2608   13
2609   1
2610   24
2611   3
2612   6
2613   7
2614   3
2615   3
2616   17
2617   1
2618   15
2619   9
2620   12
2621   1
2622   15
2623   3
2624   21
2625   17
2626   7
2627   3
2628   20
2629   3
2630   7
2631   3
2632   17
2633   1
2634   7
2635   7
2636   6
2637   6
2638   3
2639   7
2640   43
2641   3
2642   3
2643   3
2644   6
2645   6
2646   27
2647   1
2648   9
2649   3
2650   12
2651   3
2652   24
2653   3
2654   3
2655   12
2656   16
2657   1
2658   7
2659   1
2660   24
2661   3
2662   9
2663   1
2664   27
2665   7
2666   7
2667   7
2668   12
2669   3
2670   15
2671   1
2672   13
2673   16
2674   7
2675   6
2676   12
2677   1
2678   7
2679   7
2680   17
2681   3
2682   12
2683   1
2684   12
2685   7
2686   7
2687   1
2688   40
2689   1
2690   7
2691   12
2692   6
2693   1
2694   7
2695   12
2696   9
2697   7
2698   7
2699   1
2700   43
2701   3
2702   7
2703   7
2704   21
2705   3
2706   15
2707   1
2708   6
2709   12
2710   7
2711   1
2712   17
2713   1
2714   7
2715   7
2716   12
2717   7
2718   12
2719   1
2720   28
2721   3
2722   3
2723   3
2724   12
2725   6
2726   7
2727   9
2728   17
2729   1
2730   31
2731   1
2732   6
2733   3
2734   3
2735   3
2736   36
2737   7
2738   6
2739   7
2740   12
2741   1
2742   7
2743   3
2744   21
2745   12
2746   3
2747   3
2748   12
2749   1
2750   17
2751   7
2752   21
2753   1
2754   23
2755   7
2756   12
2757   3
2758   7
2759   3
2760   33
2761   3
2762   3
2763   6
2764   6
2765   7
2766   7
2767   1
2768   13
2769   7
2770   7
2771   3
2772   38
2773   3
2774   7
2775   12
2776   9
2777   1
2778   7
2779   3
2780   12
2781   9
2782   7
2783   6
2784   28
2785   3
2786   7
2787   3
2788   12
2789   1
2790   24
2791   1
2792   9
2793   12
2794   7
2795   7
2796   12
2797   1
2798   3
2799   6
2800   36
2801   1
2802   7
2803   1
2804   6
2805   15
2806   7
2807   3
2808   37
2809   3
2810   7
2811   3
2812   12
2813   3
2814   15
2815   3
2816   29
2817   6
2818   3
2819   1
2820   24
2821   7
2822   7
2823   3
2824   9
2825   6
2826   12
2827   3
2828   12
2829   7
2830   7
2831   3
2832   23
2833   1
2834   7
2835   23
2836   6
2837   1
2838   15
2839   3
2840   17
2841   3
2842   12
2843   1
2844   20
2845   3
2846   3
2847   7
2848   16
2849   7
2850   24
2851   1
2852   12
2853   6
2854   3
2855   3
2856   33
2857   1
2858   3
2859   3
2860   24
2861   1
2862   17
2863   3
2864   13
2865   7
2866   3
2867   3
2868   12
2869   3
2870   15
2871   12
2872   9
2873   6
2874   7
2875   9
2876   6
2877   7
2878   3
2879   1
2880   53
2881   3
2882   7
2883   6
2884   12
2885   3
2886   15
2887   1
2888   15
2889   9
2890   12
2891   6
2892   12
2893   3
2894   3
2895   7
2896   13
2897   1
2898   24
2899   3
2900   20
2901   3
2902   3
2903   1
2904   27
2905   7
2906   3
2907   12
2908   6
2909   1
2910   15
2911   3
2912   28
2913   3
2914   7
2915   7
2916   32
2917   1
2918   3
2919   7
2920   17
2921   3
2922   7
2923   3
2924   12
2925   20
2926   15
2927   1
2928   23
2929   3
2930   7
2931   3
2932   6
2933   3
2934   12
2935   3
2936   9
2937   7
2938   7
2939   1
2940   38
2941   3
2942   3
2943   9
2944   24
2945   7
2946   7
2947   3
2948   12
2949   3
2950   12
2951   3
2952   27
2953   1
2954   7
2955   7
2956   6
2957   1
2958   15
2959   3
2960   23
2961   12
2962   3
2963   1
2964   24
2965   3
2966   3
2967   7
2968   17
2969   1
2970   33
2971   1
2972   6
2973   3
2974   3
2975   12
2976   28
2977   3
2978   3
2979   6
2980   12
2981   3
2982   15
2983   3
2984   9
2985   7
2986   3
2987   3
2988   20
2989   6
2990   15
2991   3
2992   23
2993   3
2994   7
2995   3
2996   12
2997   13
2998   3
2999   1
3000   37

Some observations:
    s(n)=1 iff n is prime (this is because f(n) is 0 in base-b iff b divides n).
    s(n)=3 iff n is semiprime (I think).
    For n with many factors, s(n) is large.
    s(n)=0 only at n=1.

Here is a distribution of the values of s(n) for n<=3000:

Code: Select all

0   1
1   430
2   0
3   841
4   0
5   6
6   273
7   483
8   4
9   113
10   2
11   14
12   268
13   54
14   2
15   96
16   29
17   94
18   0
19   0
20   45
21   25
22   0
23   39
24   57
25   4
26   0
27   30
28   19
29   5
30   0
31   2
32   3
33   17
34   0
35   5
36   12
37   5
38   7
39   0
40   2
41   0
42   1
43   8
44   1
45   0
46   0
47   0
48   1
49   0
50   0
51   1
52   0
53   1
n>53   0

Some values occur much more often than others. 3 occurs the most often (28%), and some values (2,4,18,19,22,26,30...) do not occur at all. Do these values occur later in the sequence, or is there something special about these values? If so, what?

I am pretty fascinated by this at the moment. Any insight would be appreciated!

User avatar
chridd
Has a vermicelli title
Posts: 843
Joined: Tue Aug 19, 2008 10:07 am UTC
Location: ...Earth, I guess?
Contact:

Re: Counting Zeros

Postby chridd » Sat Aug 06, 2016 8:23 am UTC

This relates to the number's factors. A number ends in zero in base b iff it's a multiple of b, in two zeros if it's a multiple of b2, three zeros if it's a multiple of b3, etc. Therefore, s(n) can be determined knowing how many factors a number has and what powers of each factor go into the number.

This in turn means that one can determine s(n) based on the powers in the prime factorization of the number; the primes themselves don't matter. E.g., 2131 ends in one zero in base 2, base 3, and base 2×3, so s(2×3) = 3, but the fact that those primes are 2 and 3 doesn't matter, s(3×5) gives the same result, as does s(pq) for any primes p and q. Similarly, 22 ends in two zeros in base 2 and one zero in base 4, so s(22) = 2 3 [edit: fix typo], and similarly for any p2. If the powers add up to more than 2 (i.e., at least 3), then there are at least 3 factors, which means at least three zeros, so s(n) ≥ 3, so there's no possible way to get s(n) = 2. Similar (and longer and/or with more thought put into it) arguments could possibly be made for other numbers that don't occur.
~ chri d. d. /tʃɹɪ.di.di/ (Phonotactics, schmphonotactics) · she · Forum game scores
mittfh wrote:I wish this post was very quotable...

User avatar
measure
Posts: 129
Joined: Sat Apr 04, 2015 4:31 pm UTC
Location: Time-traveling kayak

Re: Counting Zeros

Postby measure » Wed Aug 10, 2016 10:00 pm UTC

UPDATE:
As chridd pointed out, the function only cares about the (order-independent) list of exponents in the parameter's prime factored form. For a given number of prime factors, each form corresponds to a partition of that number. Here I've enumerated the possible combinations up to 6 prime factors:

Spoiler:
0 factors:
    s(1)=0
    (1 form)
1 factor:
    s(a)=1
    (1 form)
2 factors:
    s(a2)=3
    s(ab)=3
    (2 forms)
3 factors:
    s(a3)=5
    s(a2b)=6
    s(abc)=7
    (3 forms)
4 factors:
    s(a4)=8
    s(a3b)=9
    s(a2b2)=11
    s(a2bc)=12
    s(abcd)=15
    (5 forms)
5 factors:
    s(a5)=10
    s(a4b)=13
    s(a3b2)=15
    s(a3bc)=17
    s(a2b2c)=20
    s(a2bcd)=24
    s(abcde)=31
    (7 forms)
6 factors:
    s(a6)=14
    s(a5b)=16
    s(a4b2)=21
    s(a4bc)=23
    s(a3b3)=21
    s(a3b2c)=27
    s(a3bcd)=33
    s(a2b2c2)=33
    s(a2b2cd)=38
    s(a2bcde)=48
    s(abcdef)=63
    (11 forms)
...

It appears to be the case that for a given number of factors k, no number with k or more factors will have a lower function value than ak. If this is true, then once I find all the function values that occur up to s(ak), I can be sure that no lower values will occur elsewhere in the function. This gives a sequence of values that never appear in the function as: 2, 4, 18, 19, 22, 26, 30, 34, 39, 46, 49, 54... I'm still not sure what's special about this numbers or how to find them quickly other than "None of these small factor patterns yielded this number because we checked them all, and all of the larger patterns will yield larger numbers".

Elmach
Posts: 155
Joined: Sun Mar 13, 2011 7:47 am UTC

Re: Counting Zeros

Postby Elmach » Fri Aug 12, 2016 4:30 am UTC

Let f:k ↦ s(ak) be the new function; that is, f(k) is the minimum value you obtain with k prime factors, assuming your conjecture holds.

Obviously, n ≤ f(n) ≤ n(n+1)/2 = Σ{k∈N: 0<k≤n} k = 1 + 2 + ... + n.

Actually, f(n) is the sum of k from 1 to n of the floor of n/k; f(n) = Σ{k∈N:0<k≤n} ⌊n/k⌋. This follows from the definition.

(The number of zeroes of an in base ak is floor(n/k).)

((I think this is O(n log n), although I will need to do more before I am sure))

A quick wolfram alpha did not give an answer. However, I have the feeling that this function is seen somewhere else. Edit: this sequence is not in the oeis.

(The largest s when given a number with n prime factors is obviously 2n - 1)

EmelinaVollmering
Posts: 11
Joined: Tue Oct 18, 2016 10:24 am UTC

Re: Counting Zeros

Postby EmelinaVollmering » Tue Oct 18, 2016 12:33 pm UTC

This is nothing related to mathematics. Suppose it as a sequence question or more specific this is a multiple sequences arranged in a certain order.

These type of questions are made to confuse the students (at least me). Where they pretend multiple questions like this one during Math-I of my 1st college year.


Return to “Mathematics”

Who is online

Users browsing this forum: Baidu [Spider] and 12 guests