Cullen and Woodall numbers: Difference between revisions
m →{{header|Phix}}: updated times using 64bit |
Realize in F# |
||
Line 40:
=={{header|F_Sharp|F#}}==
<lang fsharp>
// Cullen and Woodall numbers. Nigel Galloway: January 14th., 2022
let Cullen,Woodall=let fG n (g:int)=(bigint g)*2I**g+n in fG 1I, fG -1I
Seq.initInfinite((+)1>>Cullen)|>Seq.take 20|>Seq.iter(printf "%A "); printfn ""
Seq.initInfinite((+)1>>Woodall)|>Seq.take 20|>Seq.iter(printf "%A "); printfn ""
Seq.initInfinite((+)1)|>Seq.filter(fun n->let mutable n=Woodall n in Open.Numeric.Primes.MillerRabin.IsProbablePrime &n)|>Seq.take 12|>Seq.iter(printf "%A "); printfn ""
Seq.initInfinite((+)1)|>Seq.filter(fun n->let mutable n=Cullen n in Open.Numeric.Primes.MillerRabin.IsProbablePrime &n)|>Seq.take 5|>Seq.iter(printf "%A "); printfn ""
</lang>
{{out}}
<pre>
3 9 25 65 161 385 897 2049 4609 10241 22529 49153 106497 229377 491521 1048577 2228225 4718593 9961473 20971521
1 7 23 63 159 383 895 2047 4607 10239 22527 49151 106495 229375 491519 1048575 2228223 4718591 9961471 20971519
2 3 6 30 75 81 115 123 249 362 384 462
1 141 4713 5795 6611
</pre>
=={{header|Julia}}==
{{trans|Raku}}
|
Revision as of 12:49, 14 January 2022
A Cullen number is a number of the form n × 2n + 1 where n is a natural number.
A Woodall number is very similar. It is a number of the form n × 2n - 1 where n is a natural number.
So for each n the associated Cullen number and Woodall number differ by 2.
Woodall numbers are sometimes referred to as Riesel numbers or Cullen numbers of the second kind.
Cullen primes are Cullen numbers that are prime. Similarly, Woodall primes are Woodall numbers that are prime.
It is common to list the Cullen and Woodall primes by the value of n rather than the full evaluated expression. They tend to get very large very quickly. For example, the third Cullen prime, n == 4713, has 1423 digits when evaluated.
- Task
- Write procedures to find Cullen numbers and Woodall numbers.
- Use those procedures to find and show here, on this page the first 20 of each.
- Stretch
- Find and show the first 5 Cullen primes in terms of n.
- Find and show the first 12 Woodall primes in terms of n.
- See also
F#
<lang fsharp> // Cullen and Woodall numbers. Nigel Galloway: January 14th., 2022 let Cullen,Woodall=let fG n (g:int)=(bigint g)*2I**g+n in fG 1I, fG -1I Seq.initInfinite((+)1>>Cullen)|>Seq.take 20|>Seq.iter(printf "%A "); printfn "" Seq.initInfinite((+)1>>Woodall)|>Seq.take 20|>Seq.iter(printf "%A "); printfn "" Seq.initInfinite((+)1)|>Seq.filter(fun n->let mutable n=Woodall n in Open.Numeric.Primes.MillerRabin.IsProbablePrime &n)|>Seq.take 12|>Seq.iter(printf "%A "); printfn "" Seq.initInfinite((+)1)|>Seq.filter(fun n->let mutable n=Cullen n in Open.Numeric.Primes.MillerRabin.IsProbablePrime &n)|>Seq.take 5|>Seq.iter(printf "%A "); printfn "" </lang>
- Output:
3 9 25 65 161 385 897 2049 4609 10241 22529 49153 106497 229377 491521 1048577 2228225 4718593 9961473 20971521 1 7 23 63 159 383 895 2047 4607 10239 22527 49151 106495 229375 491519 1048575 2228223 4718591 9961471 20971519 2 3 6 30 75 81 115 123 249 362 384 462 1 141 4713 5795 6611
Julia
<lang julia>using Lazy using Primes
cullen(n, two = BigInt(2)) = n * two^n + 1 woodall(n, two = BigInt(2)) = n * two^n - 1 primecullens = @>> Lazy.range() filter(n -> isprime(cullen(n))) primewoodalls = @>> Lazy.range() filter(n -> isprime(woodall(n)))
println("First 20 Cullen numbers: ( n × 2**n + 1)\n", [cullen(n, 2) for n in 1:20]) # A002064 println("First 20 Woodall numbers: ( n × 2**n - 1)\n", [woodall(n, 2) for n in 1:20]) # A003261 println("\nFirst 5 Cullen primes: (in terms of n)\n", take(5, primecullens)) # A005849 println("\nFirst 12 Woodall primes: (in terms of n)\n", Int.(collect(take(12, primewoodalls)))) # A002234
</lang>
- Output:
First 20 Cullen numbers: ( n × 2**n + 1) [3, 9, 25, 65, 161, 385, 897, 2049, 4609, 10241, 22529, 49153, 106497, 229377, 491521, 1048577, 2228225, 4718593, 9961473, 20971521] First 20 Woodall numbers: ( n × 2**n - 1) [1, 7, 23, 63, 159, 383, 895, 2047, 4607, 10239, 22527, 49151, 106495, 229375, 491519, 1048575, 2228223, 4718591, 9961471, 20971519] First 5 Cullen primes: (in terms of n) List: (1 141 4713 5795 6611) First 12 Woodall primes: (in terms of n) [2, 3, 6, 30, 75, 81, 115, 123, 249, 362, 384, 462]
Phix
with javascript_semantics atom t0 = time() include mpfr.e procedure cullen(mpz r, integer n) mpz_ui_pow_ui(r,2,n) mpz_mul_si(r,r,n) mpz_add_si(r,r,1) end procedure procedure woodall(mpz r, integer n) cullen(r,n) mpz_sub_si(r,r,2) end procedure sequence c = {}, w = {} mpz z = mpz_init() for i=1 to 20 do cullen(z,i) c = append(c,mpz_get_str(z)) mpz_sub_si(z,z,2) w = append(w,mpz_get_str(z)) end for printf(1," Cullen[1..20]:%s\nWoodall[1..20]:%s\n",{join(c),join(w)}) atom t1 = time()+1 c = {} integer n = 1 while length(c)<iff(platform()=JS?2:5) do cullen(z,n) if mpz_prime(z) then c = append(c,sprint(n)) end if n += 1 if time()>t1 and platform()!=JS then progress("c(%d) [needs to get to 6611], %d found\r",{n,length(c)}) t1 = time()+2 end if end while if platform()!=JS then progress("") end if printf(1,"First 5 Cullen primes (in terms of n):%s\n",{join(c)}) w = {} n = 1 while length(w)<12 do woodall(z,n) if mpz_prime(z) then w = append(w,sprint(n)) end if n += 1 end while printf(1,"First 12 Woodall primes (in terms of n):%s\n",{join(w)}) ?elapsed(time()-t0)
- Output:
Cullen[1..20]:3 9 25 65 161 385 897 2049 4609 10241 22529 49153 106497 229377 491521 1048577 2228225 4718593 9961473 20971521 Woodall[1..20]:1 7 23 63 159 383 895 2047 4607 10239 22527 49151 106495 229375 491519 1048575 2228223 4718591 9961471 20971519 First 5 Cullen primes (in terms of n):1 141 4713 5795 6611 First 12 Woodall primes (in terms of n):2 3 6 30 75 81 115 123 249 362 384 462 "34.4s"
Note the time given is for desktop/Phix 64bit, for comparison the Julia entry took about 20s on the same box. On 32-bit it is nearly 5 times slower (2 minutes and 38s) and hence under pwa/p2js in a browser (which is inherently 32bit) it is limited to the first 2 cullen primes only, but manages that in 0.4s.
Raku
<lang perl6>my @cullen = ^∞ .map: { $_ × 1 +< $_ + 1 }; my @woodall = ^∞ .map: { $_ × 1 +< $_ - 1 };
put "First 20 Cullen numbers: ( n × 2**n + 1)\n", @cullen[1..20]; # A002064 put "\nFirst 20 Woodall numbers: ( n × 2**n - 1)\n", @woodall[1..20]; # A003261 put "\nFirst 5 Cullen primes: (in terms of n)\n", @cullen.grep( &is-prime, :k )[^5]; # A005849 put "\nFirst 12 Woodall primes: (in terms of n)\n", @woodall.grep( &is-prime, :k )[^12]; # A002234</lang>
- Output:
First 20 Cullen numbers: ( n × 2**n + 1) 3 9 25 65 161 385 897 2049 4609 10241 22529 49153 106497 229377 491521 1048577 2228225 4718593 9961473 20971521 First 20 Woodall numbers: ( n × 2**n - 1) 1 7 23 63 159 383 895 2047 4607 10239 22527 49151 106495 229375 491519 1048575 2228223 4718591 9961471 20971519 First 5 Cullen primes: (in terms of n) 1 141 4713 5795 6611 First 12 Woodall primes: (in terms of n) 2 3 6 30 75 81 115 123 249 362 384 462
Wren
CLI
Cullen primes limited to first 2 as very slow after that. <lang ecmascript>import "./big" for BigInt
var cullen = Fn.new { |n| (BigInt.one << n) * n + 1 }
var woodall = Fn.new { |n| cullen.call(n) - 2 }
System.print("First 20 Cullen numbers (n * 2^n + 1):") for (n in 1..20) System.write("%(cullen.call(n)) ")
System.print("\n\nFirst 20 Woodall numbers (n * 2^n - 1):") for (n in 1..20) System.write("%(woodall.call(n)) ")
System.print("\n\nFirst 2 Cullen primes (in terms of n):") var count = 0 var n = 1 while (count < 2) {
var cn = cullen.call(n) if (cn.isProbablePrime(5)){ System.write("%(n) ") count = count + 1 } n = n + 1
}
System.print("\n\nFirst 12 Woodall primes (in terms of n):") count = 0 n = 1 while (count < 12) {
var wn = woodall.call(n) if (wn.isProbablePrime(5)){ System.write("%(n) ") count = count + 1 } n = n + 1
} System.print()</lang>
- Output:
First 20 Cullen numbers (n * 2^n + 1): 3 9 25 65 161 385 897 2049 4609 10241 22529 49153 106497 229377 491521 1048577 2228225 4718593 9961473 20971521 First 20 Woodall numbers (n * 2^n - 1): 1 7 23 63 159 383 895 2047 4607 10239 22527 49151 106495 229375 491519 1048575 2228223 4718591 9961471 20971519 First 2 Cullen primes (in terms of n): 1 141 First 12 Woodall primes (in terms of n): 2 3 6 30 75 81 115 123 249 362 384 462
Embedded
Cullen primes still slow to emerge, just over 10 seconds overall. <lang ecmascript>/* cullen_and_woodall_numbers2.wren */
import "./gmp" for Mpz
var cullen = Fn.new { |n| (Mpz.one << n) * n + 1 }
var woodall = Fn.new { |n| cullen.call(n) - 2 }
System.print("First 20 Cullen numbers (n * 2^n + 1):") for (n in 1..20) System.write("%(cullen.call(n)) ")
System.print("\n\nFirst 20 Woodall numbers (n * 2^n - 1):") for (n in 1..20) System.write("%(woodall.call(n)) ")
System.print("\n\nFirst 5 Cullen primes (in terms of n):") var count = 0 var n = 1 while (count < 5) {
var cn = cullen.call(n) if (cn.probPrime(15) > 0){ System.write("%(n) ") count = count + 1 } n = n + 1
}
System.print("\n\nFirst 12 Woodall primes (in terms of n):") count = 0 n = 1 while (count < 12) {
var wn = woodall.call(n) if (wn.probPrime(15) > 0){ System.write("%(n) ") count = count + 1 } n = n + 1
} System.print()</lang>
- Output:
First 20 Cullen numbers (n * 2^n + 1): 3 9 25 65 161 385 897 2049 4609 10241 22529 49153 106497 229377 491521 1048577 2228225 4718593 9961473 20971521 First 20 Woodall numbers (n * 2^n - 1): 1 7 23 63 159 383 895 2047 4607 10239 22527 49151 106495 229375 491519 1048575 2228223 4718591 9961471 20971519 First 5 Cullen primes (in terms of n): 1 141 4713 5795 6611 First 12 Woodall primes (in terms of n): 2 3 6 30 75 81 115 123 249 362 384 462