Chowla numbers: Difference between revisions
(Added Go) |
(→{{header|Go}}: Optimized outer for loop in sieve, more than 4 times faster than before.) |
||
Line 97:
// Only interested in odd numbers >= 3
c := make([]bool, limit)
for i := 3; i*3 < limit; i += 2 {
if !c[i] && chowla(i) == 0 {
for j := 3 * i; j < limit; j += 2 * i {
|
Revision as of 15:35, 11 March 2019
Chowla numbers are also known as:
- Chowla's function
- the chowla function
- the chowla number
- the chowla sequence
The chowla number of n is (as defined by Chowla's function):
- the sum of the divisors of n excluding unity and n
- where n is a positive integer
The sequence is named after Sarvadaman D. S. Chowla, (22 October 1907 ──► 10 December 1995),
a London born Indian American mathematician specializing in number theory.
German mathematician Carl Friedrich Gauss (1777─1855) said, "Mathematics is the queen of the sciences ─ and number theory is the queen of mathematics".
- Definitions
Chowla numbers can also be expressed as:
chowla(n) = sum of divisors of n excluding unity and n chowla(n) = sum( divisors(n)) -1 - n chowla(n) = sum( properDivisors(n)) -1 chowla(n) = sum(aliquotDivisors(n)) -1 chowla(n) = aliquot(n) -1 chowla(n) = sigma(n) -1 - n chowla(n) = sigmaProperDivisiors(n) -1 chowla(a*b) = a + b, if a and b are distinct primes if chowla(n) = 0, and n > 1, then n is prime if chowla(n) = n - 1, and n > 1, then n is a perfect number
- Task
-
- create a chowla function that returns the chowla number for a positive integer n
- Find and display (1 per line) for the 1st 37 integers:
- the integer (the index)
- the chowla number for that integer
- For finding primes, use the chowla function to find values of zero
- Find and display the count of the primes up to 100
- Find and display the count of the primes up to 1,000
- Find and display the count of the primes up to 10,000
- Find and display the count of the primes up to 100,000
- Find and display the count of the primes up to 1,000,000
- Find and display the count of the primes up to 10,000,000
- For finding perfect numbers, use the chowla function to find values of n - 1
- Find and display all perfect numbers up to 35,000,000
- use commas within appropriate numbers
- show all output here
- Related tasks
- See also
-
- the OEIS entry for A48050 Chowla's function.
Go
<lang go>package main
import "fmt"
func chowla(n int) int {
if n < 1 { panic("argument nust be a positive integer") } sum := 0 for i := 2; i*i <= n; i++ { if n%i == 0 { j := n / i if i == j { sum += i } else { sum += i + j } } } return sum
}
func sieve(limit int) []bool {
// True denotes composite, false denotes prime. // Only interested in odd numbers >= 3 c := make([]bool, limit) for i := 3; i*3 < limit; i += 2 { if !c[i] && chowla(i) == 0 { for j := 3 * i; j < limit; j += 2 * i { c[j] = true } } } return c
}
func commatize(n int) string {
s := fmt.Sprintf("%d", n) le := len(s) for i := le - 3; i >= 1; i -= 3 { s = s[0:i] + "," + s[i:] } return s
}
func main() {
for i := 1; i <= 37; i++ { fmt.Printf("chowla(%2d) = %d\n", i, chowla(i)) } fmt.Println()
count := 1 limit := int(1e7) c := sieve(limit) power := 100 for i := 3; i < limit; i += 2 { if !c[i] { count++ } if i == power-1 { fmt.Printf("Count of primes up to %-10s = %s\n", commatize(power), commatize(count)) power *= 10 } }
fmt.Println() count = 0 limit = 35000000 for i := uint(2); ; i++ { p := 1 << (i - 1) * (1<= limit { break } if chowla(p) == p-1 { fmt.Printf("%s is a perfect number\n", commatize(p)) count++ } } fmt.Println("There are", count, "perfect numbers <= 35,000,000")
}</lang>
- Output:
chowla( 1) = 0 chowla( 2) = 0 chowla( 3) = 0 chowla( 4) = 2 chowla( 5) = 0 chowla( 6) = 5 chowla( 7) = 0 chowla( 8) = 6 chowla( 9) = 3 chowla(10) = 7 chowla(11) = 0 chowla(12) = 15 chowla(13) = 0 chowla(14) = 9 chowla(15) = 8 chowla(16) = 14 chowla(17) = 0 chowla(18) = 20 chowla(19) = 0 chowla(20) = 21 chowla(21) = 10 chowla(22) = 13 chowla(23) = 0 chowla(24) = 35 chowla(25) = 5 chowla(26) = 15 chowla(27) = 12 chowla(28) = 27 chowla(29) = 0 chowla(30) = 41 chowla(31) = 0 chowla(32) = 30 chowla(33) = 14 chowla(34) = 19 chowla(35) = 12 chowla(36) = 54 chowla(37) = 0 Count of primes up to 100 = 25 Count of primes up to 1,000 = 168 Count of primes up to 10,000 = 1,229 Count of primes up to 100,000 = 9,592 Count of primes up to 1,000,000 = 78,498 Count of primes up to 10,000,000 = 664,579 6 is a perfect number 28 is a perfect number 496 is a perfect number 8,128 is a perfect number 33,550,336 is a perfect number There are 5 perfect numbers <= 35,000,000
Julia
<lang julia>using Primes, Formatting
function chowla(n)
if n < 1 throw("Chowla function argument must be positive") elseif n < 4 return zero(n) else f = [one(n)] for (p,e) in factor(n) f = reduce(vcat, [f*p^j for j in 1:e], init=f) end return sum(f) - one(n) - n end
end
function countchowlas(n, asperfect=false, verbose=false)
count = 0 for i in 2:n # 1 is not prime or perfect so skip chow = chowla(i) if (asperfect && chow == i - 1) || (!asperfect && chow == 0) count += 1 verbose && println("The number $(format(i, commas=true)) is ", asperfect ? "perfect." : "prime.") end end count
end
function testchowla()
println("The first 37 chowla numbers are:") for i in 1:37 println("Chowla($i) is ", chowla(i)) end for i in [100, 1000, 10000, 100000, 1000000, 10000000] println("The count of the primes up to $(format(i, commas=true)) is $(format(countchowlas(i), commas=true))") end println("The count of perfect numbers up to 35,000,000 is $(countchowlas(35000000, true, true)).")
end
testchowla()
</lang>
- Output:
The first 37 chowla numbers are: Chowla(1) is 0 Chowla(2) is 0 Chowla(3) is 0 Chowla(4) is 2 Chowla(5) is 0 Chowla(6) is 5 Chowla(7) is 0 Chowla(8) is 6 Chowla(9) is 3 Chowla(10) is 7 Chowla(11) is 0 Chowla(12) is 15 Chowla(13) is 0 Chowla(14) is 9 Chowla(15) is 8 Chowla(16) is 14 Chowla(17) is 0 Chowla(18) is 20 Chowla(19) is 0 Chowla(20) is 21 Chowla(21) is 10 Chowla(22) is 13 Chowla(23) is 0 Chowla(24) is 35 Chowla(25) is 5 Chowla(26) is 15 Chowla(27) is 12 Chowla(28) is 27 Chowla(29) is 0 Chowla(30) is 41 Chowla(31) is 0 Chowla(32) is 30 Chowla(33) is 14 Chowla(34) is 19 Chowla(35) is 12 Chowla(36) is 54 Chowla(37) is 0 The count of the primes up to 100 is 25 The count of the primes up to 1,000 is 168 The count of the primes up to 10,000 is 1,229 The count of the primes up to 100,000 is 9,592 The count of the primes up to 1,000,000 is 78,498 The count of the primes up to 10,000,000 is 664,579 The number 6 is perfect. The number 28 is perfect. The number 496 is perfect. The number 8,128 is perfect. The number 33,550,336 is perfect. The count of perfect numbers up to 35,000,000 is 5.
REXX
<lang rexx>/*REXX program computes/displays chowla numbers (and may count primes & perfect numbers.*/ parse arg LO HI . /*obtain optional arguments from the CL*/ if LO== | LO=="," then LO= 1 /*Not specified? Then use the default.*/ perf= LO<0; LO= abs(LO) /*Negative? Then determine if perfect.*/ if HI== | HI=="," then HI= LO /*Not specified? Then use the default.*/ prim= HI<0; HI= abs(HI) /*Negative? Then determine if a prime.*/ numeric digits max(9, length(HI) + 1 ) /*use enough decimal digits for // */ w= length( commas(HI) ) /*W: used in aligning output numbers.*/ tell= \(prim | perf) /*set boolean value for showing chowlas*/ p= 0 /*the number of primes found (so far).*/
do j=LO to HI; #= chowla(j) /*compute the cholwa number for J. */ if tell then say right('chowla('commas(j)")", w+9) ' = ' right( commas(#), w) else if #==0 then if j>1 then p= p+1 if perf then if j-1==# & j>1 then say right(commas(j), w) ' is a perfect number.' end /*j*/
if prim & \perf then say 'number of primes found for the range ' commas(LO) " to " ,
commas(HI) " (inclusive) is: " commas(p)
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ chowla: procedure; parse arg x; if x<2 then return 0; odd= x // 2
s=0 /* [↓] use EVEN or ODD integers. ___*/ do k=2+odd by 1+odd while k*k<x /*divide by all the integers up to √ X */ if x//k==0 then s=s + k + x%k /*add the two divisors to the sum. */ end /*k*/ /* [↓] adkust for square. ___*/ if k*k==x then s=s + k /*Was X a square? If so, add √ X */ return s /*return " " " " " */
/*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do k=length(_)-3 to 1 by -3; _= insert(',', _, k); end; return _</lang>
- output when using the input of: 1 37
chowla(1) = 0 chowla(2) = 0 chowla(3) = 0 chowla(4) = 2 chowla(5) = 0 chowla(6) = 5 chowla(7) = 0 chowla(8) = 6 chowla(9) = 3 chowla(10) = 7 chowla(11) = 0 chowla(12) = 15 chowla(13) = 0 chowla(14) = 9 chowla(15) = 8 chowla(16) = 14 chowla(17) = 0 chowla(18) = 20 chowla(19) = 0 chowla(20) = 21 chowla(21) = 10 chowla(22) = 13 chowla(23) = 0 chowla(24) = 35 chowla(25) = 5 chowla(26) = 15 chowla(27) = 12 chowla(28) = 27 chowla(29) = 0 chowla(30) = 41 chowla(31) = 0 chowla(32) = 30 chowla(33) = 14 chowla(34) = 19 chowla(35) = 12 chowla(36) = 54 chowla(37) = 0
- output when using the input of: 1 -100
number of primes found for the range 1 to 100 (inclusive) is: 25
- output when using the input of: 1 -1,000
number of primes found for the range 1 to 1,000 (inclusive) is: 168
- output when using the input of: 1 -10,000
number of primes found for the range 1 to 10,000 (inclusive) is: 1,229
- output when using the input of: 1 -100,000
number of primes found for the range 1 to 100,000 (inclusive) is: 9,592
- output when using the input of: 1 -1,000,000
number of primes found for the range 1 to 1,000,000 (inclusive) is: 78.498
- output when using the input of: 1 -10,000,000
number of primes found for the range 1 to 10,000,000 (inclusive) is: 664,579
- output when using the input of: -1 35,000,000
6 is a perfect number. 28 is a perfect number. 496 is a perfect number. 8,128 is a perfect number. 33,550,336 is a perfect number.