Direct function: Difference between revisions

Revision as of 10:08, 28 October 2019

Revision as of 15:32, 28 October 2019

Line 182:

The last sequence, the number of primes less than powers of 10, is an initial segment of {{OEIS2C|id=A006880}}. The last number, 50847534, is the number of primes less than <math>10^9</math>. It is called Bertelsen's number, memorably described by [[MathWorld]] as "an erroneous name erroneously given the erroneous value of <math>\pi(10^9) = 50847478</math>".<ref name=MathWorld>{{citation|last=Weisstein|first=Eric W.|title=Bertelsen's Number|publisher=MathWorld, A Wolfram Web Resource|url=http://mathworld.wolfram.com/BertelsensNumber.html|access-date=26 September 2019}}</ref>

{{code|sieve|apl}} uses two different methods to mark composites with 0s, both effected using local anonymous dfns: The first uses the [[sieve of Eratosthenes]] on an initial mask of 1 and a prefix of the primes 2&nbsp;3...43, using the ''insert'' operator {{code|⌿|apl}} ([[foldFold (higher-order function)|right fold]]{{dn|date=October 2019}}). (The length of the prefix obtains by comparison with the [[primorial|primorial function]] {{code|×⍀p|apl}}.) The second finds the smallest new prime {{code|q|apl}} remaining in {{code|b|apl}} ({{code|q←b⍳1|apl}}), and sets to 0 bit {{code|q|apl}} itself and bits at {{code|q|apl}} times the numbers at remaining 1 bits in an initial segment of {{code|b|apl}} ({{code|⍸b↑⍨⌈n÷q|apl}}). This second dfn uses tail recursion.

=== Tail recursion ===