1488:
427:
929:
1074:
265:
1498:
A hollow sphere the size of the planet Earth filled with fine sand would have around 10 grains. A volume the size of the observable universe would have around 10 grains of sand. There might be room for 10 quantum strings in such a universe.
714:
574:
773:
141:
1613:
1251:
1286:
For example, 1,000,000,003 = 23 × 307 × 141623. The following table provides a numerical summary of the growth of the average number of distinct prime factors of a natural number
761:
940:
241:
422:{\displaystyle \lim _{x\rightarrow \infty }\left({\frac {1}{x}}\cdot \#\left\{n\leq x:a\leq {\frac {\omega (n)-\log \log n}{\sqrt {\log \log n}}}\leq b\right\}\right)=\Phi (a,b)}
465:
177:
1550:
1148:
594:
1523:
1324:
1304:
473:
924:{\displaystyle \lim _{x\rightarrow \infty }\left({\frac {1}{x}}\cdot \#\left\{n\leq x:a\leq {\frac {f(n)-A(n)}{B(n)}}\leq b\right\}\right)=\Phi (a,b)}
184:
1563:
1495:
Around 12.6% of 10,000 digit numbers are constructed from 10 distinct prime numbers and around 68% are constructed from between 7 and 13 primes.
192:
1812:
1735:
76:
1156:
1673:
1727:
1505:
It is very difficult if not impossible to discover the Erdős-Kac theorem empirically, as the
Gaussian only shows up when
1807:
188:
47:
1283:
The Erdős–Kac theorem means that the construction of a number around one billion requires on average three primes.
1069:{\displaystyle A(n)=\sum _{p\leq n}{\frac {f(p)}{p}},\qquad B(n)={\sqrt {\sum _{p\leq n}{\frac {f(p)^{2}}{p}}}}.}
719:
67:
1718:
Kuo, Wentang; Liu, Yu-Ru (2008). "The Erdős–Kac theorem and its generalizations". In De
Koninck, Jean-Marie;
210:
1802:
1560:
showed that the best possible uniform asymptotic bound on the error in the approximation to a
Gaussian is
1265:
1502:
Numbers of this magnitude—with 186 digits—would require on average only 6 primes for construction.
1261:
147:
1698:
1553:
435:
153:
1770:
1731:
1690:
1528:
588:
1741:
1719:
1706:
1682:
1647:
1671:(1940). "The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions".
1126:
709:{\displaystyle \scriptstyle f(p_{1}^{a_{1}}\cdots p_{k}^{a_{k}})=f(p_{1})+\cdots +f(p_{k})}
1745:
1710:
1557:
1787:
1508:
1491:
A spreading
Gaussian distribution of distinct primes illustrating the Erdos-Kac theorem
1309:
1289:
1773:
1796:
1664:
39:
31:
1724:
Anatomy of integers. Based on the CRM workshop, Montreal, Canada, March 13--17, 2006
1632:
1268:
guarantees that after appropriate rescaling, the above expression will be
Gaussian.
1092:
is approximately normally distributed with mean and variance log log
1272:
569:{\displaystyle \Phi (a,b)={\frac {1}{\sqrt {2\pi }}}\int _{a}^{b}e^{-t^{2}/2}\,dt.}
59:
1088:
is a randomly chosen large integer, then the number of distinct prime factors of
17:
1788:
Timothy Gowers: The
Importance of Mathematics (part 6, 4 mins in) and (part 7)
1694:
1778:
1256:
This sum counts how many distinct prime factors our random natural number
1668:
1651:
43:
1702:
136:{\displaystyle {\frac {\omega (n)-\log \log n}{\sqrt {\log \log n}}}}
1686:
1487:
1755:
Statistical
Independence in Probability, Analysis and Number Theory
1726:. CRM Proceedings and Lecture Notes. Vol. 46. Providence, RI:
1486:
1608:{\displaystyle O\left({\frac {1}{\sqrt {\log \log n}}}\right).}
1246:{\displaystyle I_{n_{2}}+I_{n_{3}}+I_{n_{5}}+I_{n_{7}}+\ldots }
1096:. This comes from the fact that given a random natural number
1150:, consider the following sum of indicator random variables:
180:
1084:
Intuitively, Kac's heuristic for the result says that if
467:
is the normal (or "Gaussian") distribution, defined as
723:
598:
1566:
1531:
1511:
1312:
1292:
1159:
1129:
943:
776:
722:
597:
476:
438:
268:
213:
156:
79:
1271:
The actual proof of the theorem, due to Erdős, uses
1328:
1607:
1544:
1517:
1318:
1298:
1245:
1142:
1068:
923:
755:
708:
568:
459:
421:
235:
171:
135:
27:Fundamental theorem of probabilistic number theory
1260:has. It can be shown that this sum satisfies the
778:
270:
46:, and also known as the fundamental theorem of
8:
1574:
1565:
1536:
1530:
1510:
1311:
1291:
1229:
1224:
1209:
1204:
1189:
1184:
1169:
1164:
1158:
1134:
1128:
1049:
1033:
1021:
1015:
975:
963:
942:
837:
798:
781:
775:
756:{\displaystyle \scriptstyle |f(p)|\leq 1}
741:
724:
721:
696:
668:
644:
639:
634:
619:
614:
609:
596:
556:
546:
540:
532:
522:
517:
498:
475:
437:
329:
290:
273:
267:
214:
212:
155:
80:
78:
1623:
1275:to make rigorous the above intuition.
236:{\displaystyle {\sqrt {\log \log n}}}
7:
1115:Now, denoting the event "the number
1388:1,000,000,000,000,000,000,000,000
1079:
903:
811:
788:
477:
439:
401:
303:
280:
25:
1674:American Journal of Mathematics
1266:Lindeberg central limit theorem
999:
187:.) This is an extension of the
1046:
1039:
1009:
1003:
987:
981:
953:
947:
918:
906:
878:
872:
864:
858:
849:
843:
785:
742:
738:
732:
725:
702:
689:
674:
661:
652:
602:
492:
480:
454:
442:
416:
404:
341:
335:
277:
166:
160:
92:
86:
66:, then, loosely speaking, the
1:
1728:American Mathematical Society
1631:Rényi, A.; Turán, P. (1958).
207:with a typical error of size
1813:Theorems about prime numbers
1525:starts getting to be around
58:) is the number of distinct
1757:. John Wiley and Sons, Inc.
1633:"On a theorem of Erdös-Kac"
1104:is divisible by some prime
48:probabilistic number theory
1829:
1112:are mutually independent.
460:{\displaystyle \Phi (a,b)}
172:{\displaystyle \omega (n)}
1100:, the events "the number
1722:; Luca, Florian (eds.).
1545:{\displaystyle 10^{100}}
1080:Kac's original heuristic
191:, which states that the
68:probability distribution
203:) is log log
189:Hardy–Ramanujan theorem
1609:
1546:
1519:
1492:
1320:
1300:
1247:
1144:
1070:
925:
757:
710:
570:
461:
423:
237:
173:
137:
1610:
1547:
1520:
1490:
1321:
1301:
1248:
1145:
1143:{\displaystyle n_{p}}
1071:
926:
758:
711:
571:
462:
424:
238:
174:
138:
1730:. pp. 209–216.
1652:10.4064/aa-4-1-71-84
1564:
1529:
1509:
1310:
1290:
1264:, and therefore the
1157:
1127:
941:
774:
720:
595:
474:
436:
266:
211:
154:
77:
1808:Normal distribution
1774:"Erdős–Kac Theorem"
1348:of distinct primes
1262:Lindeberg condition
651:
626:
579:More generally, if
527:
148:normal distribution
1771:Weisstein, Eric W.
1753:Kac, Mark (1959).
1605:
1552:. More precisely,
1542:
1515:
1493:
1316:
1296:
1279:Numerical examples
1243:
1140:
1066:
1032:
974:
921:
792:
753:
752:
706:
705:
630:
605:
566:
513:
457:
419:
284:
233:
169:
133:
1737:978-0-8218-4406-9
1720:Granville, Andrew
1596:
1595:
1518:{\displaystyle n}
1485:
1484:
1319:{\displaystyle n}
1299:{\displaystyle n}
1061:
1059:
1017:
994:
959:
882:
806:
777:
589:additive function
511:
510:
380:
379:
298:
269:
247:Precise statement
231:
131:
130:
50:, states that if
36:Erdős–Kac theorem
18:Erdős-Kac theorem
16:(Redirected from
1820:
1784:
1783:
1758:
1749:
1714:
1681:(1/4): 738–742.
1656:
1655:
1640:Acta Arithmetica
1637:
1628:
1614:
1612:
1611:
1606:
1601:
1597:
1579:
1575:
1551:
1549:
1548:
1543:
1541:
1540:
1524:
1522:
1521:
1516:
1329:
1325:
1323:
1322:
1317:
1306:with increasing
1305:
1303:
1302:
1297:
1252:
1250:
1249:
1244:
1236:
1235:
1234:
1233:
1216:
1215:
1214:
1213:
1196:
1195:
1194:
1193:
1176:
1175:
1174:
1173:
1149:
1147:
1146:
1141:
1139:
1138:
1119:is divisible by
1075:
1073:
1072:
1067:
1062:
1060:
1055:
1054:
1053:
1034:
1031:
1016:
995:
990:
976:
973:
930:
928:
927:
922:
899:
895:
894:
890:
883:
881:
867:
838:
807:
799:
791:
762:
760:
759:
754:
745:
728:
715:
713:
712:
707:
701:
700:
673:
672:
650:
649:
648:
638:
625:
624:
623:
613:
587:) is a strongly
575:
573:
572:
567:
555:
554:
550:
545:
544:
526:
521:
512:
503:
499:
466:
464:
463:
458:
428:
426:
425:
420:
397:
393:
392:
388:
381:
363:
362:
330:
299:
291:
283:
255: <
242:
240:
239:
234:
232:
215:
178:
176:
175:
170:
146:is the standard
142:
140:
139:
134:
132:
114:
113:
81:
21:
1828:
1827:
1823:
1822:
1821:
1819:
1818:
1817:
1793:
1792:
1769:
1768:
1765:
1752:
1738:
1717:
1687:10.2307/2371483
1663:
1660:
1659:
1635:
1630:
1629:
1625:
1620:
1570:
1562:
1561:
1532:
1527:
1526:
1507:
1506:
1346:Average number
1308:
1307:
1288:
1287:
1281:
1225:
1220:
1205:
1200:
1185:
1180:
1165:
1160:
1155:
1154:
1130:
1125:
1124:
1082:
1045:
1035:
977:
939:
938:
868:
839:
818:
814:
797:
793:
772:
771:
718:
717:
692:
664:
640:
615:
593:
592:
536:
528:
472:
471:
434:
433:
331:
310:
306:
289:
285:
264:
263:
249:
209:
208:
152:
151:
82:
75:
74:
28:
23:
22:
15:
12:
11:
5:
1826:
1824:
1816:
1815:
1810:
1805:
1795:
1794:
1791:
1790:
1785:
1764:
1763:External links
1761:
1760:
1759:
1750:
1736:
1715:
1658:
1657:
1622:
1621:
1619:
1616:
1604:
1600:
1594:
1591:
1588:
1585:
1582:
1578:
1573:
1569:
1539:
1535:
1514:
1483:
1482:
1479:
1476:
1473:
1469:
1468:
1465:
1462:
1459:
1455:
1454:
1451:
1448:
1445:
1441:
1440:
1437:
1434:
1431:
1427:
1426:
1423:
1420:
1417:
1413:
1412:
1409:
1406:
1403:
1399:
1398:
1395:
1392:
1389:
1385:
1384:
1381:
1378:
1375:
1374:1,000,000,000
1371:
1370:
1367:
1364:
1361:
1357:
1356:
1350:
1344:
1335:
1315:
1295:
1280:
1277:
1254:
1253:
1242:
1239:
1232:
1228:
1223:
1219:
1212:
1208:
1203:
1199:
1192:
1188:
1183:
1179:
1172:
1168:
1163:
1137:
1133:
1081:
1078:
1077:
1076:
1065:
1058:
1052:
1048:
1044:
1041:
1038:
1030:
1027:
1024:
1020:
1014:
1011:
1008:
1005:
1002:
998:
993:
989:
986:
983:
980:
972:
969:
966:
962:
958:
955:
952:
949:
946:
932:
931:
920:
917:
914:
911:
908:
905:
902:
898:
893:
889:
886:
880:
877:
874:
871:
866:
863:
860:
857:
854:
851:
848:
845:
842:
836:
833:
830:
827:
824:
821:
817:
813:
810:
805:
802:
796:
790:
787:
784:
780:
763:for all prime
751:
748:
744:
740:
737:
734:
731:
727:
704:
699:
695:
691:
688:
685:
682:
679:
676:
671:
667:
663:
660:
657:
654:
647:
643:
637:
633:
629:
622:
618:
612:
608:
604:
601:
577:
576:
565:
562:
559:
553:
549:
543:
539:
535:
531:
525:
520:
516:
509:
506:
502:
497:
494:
491:
488:
485:
482:
479:
456:
453:
450:
447:
444:
441:
430:
429:
418:
415:
412:
409:
406:
403:
400:
396:
391:
387:
384:
378:
375:
372:
369:
366:
361:
358:
355:
352:
349:
346:
343:
340:
337:
334:
328:
325:
322:
319:
316:
313:
309:
305:
302:
297:
294:
288:
282:
279:
276:
272:
251:For any fixed
248:
245:
230:
227:
224:
221:
218:
168:
165:
162:
159:
144:
143:
129:
126:
123:
120:
117:
112:
109:
106:
103:
100:
97:
94:
91:
88:
85:
38:, named after
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1825:
1814:
1811:
1809:
1806:
1804:
1801:
1800:
1798:
1789:
1786:
1781:
1780:
1775:
1772:
1767:
1766:
1762:
1756:
1751:
1747:
1743:
1739:
1733:
1729:
1725:
1721:
1716:
1712:
1708:
1704:
1700:
1696:
1692:
1688:
1684:
1680:
1676:
1675:
1670:
1666:
1662:
1661:
1653:
1649:
1645:
1641:
1634:
1627:
1624:
1617:
1615:
1602:
1598:
1592:
1589:
1586:
1583:
1580:
1576:
1571:
1567:
1559:
1555:
1537:
1533:
1512:
1503:
1500:
1496:
1489:
1480:
1477:
1474:
1471:
1470:
1466:
1463:
1460:
1457:
1456:
1452:
1449:
1446:
1443:
1442:
1438:
1435:
1432:
1429:
1428:
1424:
1421:
1418:
1415:
1414:
1410:
1407:
1404:
1401:
1400:
1396:
1393:
1390:
1387:
1386:
1382:
1379:
1376:
1373:
1372:
1368:
1365:
1362:
1359:
1358:
1355:
1351:
1349:
1345:
1343:
1342:
1336:
1334:
1331:
1330:
1327:
1313:
1293:
1284:
1278:
1276:
1274:
1269:
1267:
1263:
1259:
1240:
1237:
1230:
1226:
1221:
1217:
1210:
1206:
1201:
1197:
1190:
1186:
1181:
1177:
1170:
1166:
1161:
1153:
1152:
1151:
1135:
1131:
1122:
1118:
1113:
1111:
1107:
1103:
1099:
1095:
1091:
1087:
1063:
1056:
1050:
1042:
1036:
1028:
1025:
1022:
1018:
1012:
1006:
1000:
996:
991:
984:
978:
970:
967:
964:
960:
956:
950:
944:
937:
936:
935:
915:
912:
909:
900:
896:
891:
887:
884:
875:
869:
861:
855:
852:
846:
840:
834:
831:
828:
825:
822:
819:
815:
808:
803:
800:
794:
782:
770:
769:
768:
766:
749:
746:
735:
729:
697:
693:
686:
683:
680:
677:
669:
665:
658:
655:
645:
641:
635:
631:
627:
620:
616:
610:
606:
599:
590:
586:
582:
563:
560:
557:
551:
547:
541:
537:
533:
529:
523:
518:
514:
507:
504:
500:
495:
489:
486:
483:
470:
469:
468:
451:
448:
445:
413:
410:
407:
398:
394:
389:
385:
382:
376:
373:
370:
367:
364:
359:
356:
353:
350:
347:
344:
338:
332:
326:
323:
320:
317:
314:
311:
307:
300:
295:
292:
286:
274:
262:
261:
260:
258:
254:
246:
244:
228:
225:
222:
219:
216:
206:
202:
198:
194:
190:
186:
182:
163:
157:
149:
127:
124:
121:
118:
115:
110:
107:
104:
101:
98:
95:
89:
83:
73:
72:
71:
69:
65:
61:
60:prime factors
57:
53:
49:
45:
41:
37:
33:
32:number theory
19:
1777:
1754:
1723:
1678:
1672:
1646:(1): 71–84.
1643:
1639:
1626:
1504:
1501:
1497:
1494:
1433:210,704,569
1353:
1347:
1340:
1338:
1332:
1285:
1282:
1273:sieve theory
1270:
1257:
1255:
1120:
1116:
1114:
1109:
1108:" for each
1105:
1101:
1097:
1093:
1089:
1085:
1083:
933:
764:
584:
580:
578:
431:
256:
252:
250:
204:
200:
196:
193:normal order
179:is sequence
145:
63:
55:
51:
35:
29:
1665:Erdős, Paul
1803:Paul Erdős
1797:Categories
1746:1187.11024
1711:0024.10203
1618:References
1354:deviation
1339:digits in
1337:Number of
40:Paul Erdős
1779:MathWorld
1695:0002-9327
1669:Kac, Mark
1590:
1584:
1352:Standard
1241:…
1026:≤
1019:∑
968:≤
961:∑
904:Φ
885:≤
853:−
835:≤
823:≤
812:#
809:⋅
789:∞
786:→
747:≤
681:⋯
628:⋯
534:−
515:∫
508:π
478:Φ
440:Φ
402:Φ
383:≤
374:
368:
357:
351:
345:−
333:ω
327:≤
315:≤
304:#
301:⋅
281:∞
278:→
226:
220:
158:ω
125:
119:
108:
102:
96:−
84:ω
44:Mark Kac
1703:2371483
1475:10 + 1
1461:10 + 1
1447:10 + 1
767:, then
716:) with
183:in the
181:A001221
1744:
1734:
1709:
1701:
1693:
1419:9,567
1360:1,000
432:where
34:, the
1699:JSTOR
1636:(PDF)
1558:Turán
1554:Rényi
1481:31.6
1478:1000
1123:" by
934:with
1732:ISBN
1691:ISSN
1556:and
1464:100
1453:7.1
1439:4.5
1425:3.2
1411:2.2
1383:1.7
1369:1.4
185:OEIS
42:and
1742:Zbl
1707:Zbl
1683:doi
1648:doi
1587:log
1581:log
1538:100
1472:10
1467:10
1458:10
1450:50
1444:10
1436:20
1430:10
1422:10
1416:10
1405:66
1402:10
1391:25
1377:10
779:lim
371:log
365:log
354:log
348:log
271:lim
223:log
217:log
195:of
150:. (
122:log
116:log
105:log
99:log
70:of
62:of
30:In
1799::
1776:.
1740:.
1705:.
1697:.
1689:.
1679:62
1677:.
1667:;
1642:.
1638:.
1534:10
1408:5
1397:2
1394:4
1380:3
1366:2
1363:4
1326:.
259:,
243:.
1782:.
1748:.
1713:.
1685::
1654:.
1650::
1644:4
1603:.
1599:)
1593:n
1577:1
1572:(
1568:O
1513:n
1341:n
1333:n
1314:n
1294:n
1258:n
1238:+
1231:7
1227:n
1222:I
1218:+
1211:5
1207:n
1202:I
1198:+
1191:3
1187:n
1182:I
1178:+
1171:2
1167:n
1162:I
1136:p
1132:n
1121:p
1117:n
1110:p
1106:p
1102:n
1098:n
1094:n
1090:n
1086:n
1064:.
1057:p
1051:2
1047:)
1043:p
1040:(
1037:f
1029:n
1023:p
1013:=
1010:)
1007:n
1004:(
1001:B
997:,
992:p
988:)
985:p
982:(
979:f
971:n
965:p
957:=
954:)
951:n
948:(
945:A
919:)
916:b
913:,
910:a
907:(
901:=
897:)
892:}
888:b
879:)
876:n
873:(
870:B
865:)
862:n
859:(
856:A
850:)
847:n
844:(
841:f
832:a
829::
826:x
820:n
816:{
804:x
801:1
795:(
783:x
765:p
750:1
743:|
739:)
736:p
733:(
730:f
726:|
703:)
698:k
694:p
690:(
687:f
684:+
678:+
675:)
670:1
666:p
662:(
659:f
656:=
653:)
646:k
642:a
636:k
632:p
621:1
617:a
611:1
607:p
603:(
600:f
591:(
585:n
583:(
581:f
564:.
561:t
558:d
552:2
548:/
542:2
538:t
530:e
524:b
519:a
505:2
501:1
496:=
493:)
490:b
487:,
484:a
481:(
455:)
452:b
449:,
446:a
443:(
417:)
414:b
411:,
408:a
405:(
399:=
395:)
390:}
386:b
377:n
360:n
342:)
339:n
336:(
324:a
321::
318:x
312:n
308:{
296:x
293:1
287:(
275:x
257:b
253:a
229:n
205:n
201:n
199:(
197:ω
167:)
164:n
161:(
128:n
111:n
93:)
90:n
87:(
64:n
56:n
54:(
52:ω
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
