Chowla numbers: Difference between revisions

Content added Content deleted

Inline

Revision as of 13:58, 12 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.
Perl 6
Oh cool! We're including random, irrelevant quotes! 😎
"There are two hard problems in computer science: cache invalidation, naming things, and off-by-1 errors." ~Leon Bambrick
Much like in the Totient function task, we are using a thing poorly suited to finding prime numbers, to find prime numbers, and we're going ALL IN, BABY!
(For a more reasonable test, reduce the orders-of-magnitude range in the "Primes count" line from 2..7 to 2..5)

<lang perl6>sub comma { $^i.flip.comb(3).join(',').flip }
sub schnitzel (\Radda, \radDA = 0) {
Radda.is-prime ?? !Radda !! ?radDA ?? Radda !! sum flat (2 .. Radda.sqrt.floor).map: -> \RAdda { my \RADDA = Radda div RAdda; next if RADDA * RAdda !== Radda; RAdda !== RADDA ?? (RAdda, RADDA) !! RADDA }
}
my \chowder = cache (1..Inf).hyper(:8degree).grep( !*.&schnitzel: 'panini' );
my \mung-daal = lazy gather for chowder -> \panini {
my \gazpacho = 2**panini - 1; take gazpacho * 2**(panini - 1) unless schnitzel gazpacho, panini;
}
printf "chowla(%2d) = %2d\n", $_, .&schnitzel for 1..37;
say ;
printf "Count of primes up to %10s: %s\n", comma(10**$_),
comma chowder.first( * > 10**$_, :k) for 2..7;
say "\nPerfect numbers less than 35,000,000";
.&comma.say for mung-daal[^5];</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 Perfect numbers less than 35,000,000 6 28 496 8,128 33,550,336
Python
Uses underscores to separate digits in numbers, and th sympy library to aid calculations.
<lang python># https://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.factor_.divisors from sympy import divisors
def chowla(n):
return 0 if n < 2 else sum(divisors(n, generator=True)) - 1 -n
def is_prime(n):
return chowla(n) == 0
def primes_to(n):
return sum(chowla(i) == 0 for i in range(2, n))
def perfect_between(n, m):
c = 0 print(f"\nPerfect numbers between [{n:_}, {m:_})") for i in range(n, m): if i > 1 and chowla(i) == i - 1: print(f" {i:_}") c += 1 print(f"Found {c} Perfect numbers between [{n:_}, {m:_})")
if __name__ == '__main__':
for i in range(1, 38): print(f"chowla({i:2}) == {chowla(i)}") for i in range(2, 6): print(f"primes_to({10**i:_}) == {primes_to(10**i):_}") perfect_between(1, 1_000_000) print() for i in range(6, 8): print(f"primes_to({10**i:_}) == {primes_to(10**i):_}") perfect_between(1_000_000, 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 primes_to(100) == 25 primes_to(1_000) == 168 primes_to(10_000) == 1_229 primes_to(100_000) == 9_592 Perfect numbers between [1, 1_000_000) 6 28 496 8_128 Found 4 Perfect numbers between [1, 1_000_000) primes_to(1_000_000) == 78_498 primes_to(10_000_000) == 664_579 Perfect numbers between [1_000_000, 35_000_000) 33_550_336 Found 1 Perfect numbers between [1_000_000, 35_000_000)
Python: Numba
(Elementary) use of the numba library needs
library install and import

use of `@jit` decorator on some functions

Rewrite to remove use of `sum()`

Splitting one function for the jit compiler to digest.
<lang python>from numba import jit
https://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.factor_.divisors
from sympy import divisors
@jit def chowla(n):
return 0 if n < 2 else sum(divisors(n, generator=True)) - 1 -n
@jit def is_prime(n):
return chowla(n) == 0
@jit def primes_to(n):
acc = 0 for i in range(2, n): if chowla(i) == 0: acc += 1 return acc
@jit def _perfect_between(n, m):
for i in range(n, m): if i > 1 and chowla(i) == i - 1: yield i
def perfect_between(n, m):
c = 0 print(f"\nPerfect numbers between [{n:_}, {m:_})") for i in _perfect_between(n, m): print(f" {i:_}") c += 1 print(f"Found {c} Perfect numbers between [{n:_}, {m:_})")</lang>

Output:
Same as above for use of same __main__ block.
Speedup - not much, subjectively...
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 308: / Line 308: @@
 <blockquote>"There are two hard problems in computer science: cache invalidation, naming things, and off-by-1 errors." ~Leon Bambrick</blockquote>
-Much like in the [[Totient_function|Totient function]] task, we are using thing poorly suited to finding prime numbers, to find prime numbers, and we're going ALL IN, BABY!
+Much like in the [[Totient_function|Totient function]] task, we are using a thing poorly suited to finding prime numbers, to find prime numbers, and we're going ALL IN, BABY!
 (For a more reasonable test, reduce the orders-of-magnitude range in the "Primes count" line from 2..7 to 2..5)