Chowla numbers: Difference between revisions

Content added Content deleted

Inline

Revision as of 16:28, 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 1^st 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 must 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.

@@ Line 142: / Line 142: @@
     for i := uint(2); ; i++ {
         p := 1 << (i - 1) * (1<<i - 1) // perfect numbers must be of this form
-        if p >= limit {
+        if p > limit {
             break
         }