Chowla numbers are also known as:

   Chowla's function
   chowla numbers 
   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

    totient function
    perfect numbers
   Proper divisors
   Sieve of Eratosthenes


See also

   the OEIS entry for   A48050 Chowla's function.


#COMPILE EXE
#DIM ALL
#COMPILER PBCC 6
 
FUNCTION chowla(BYVAL n AS LONG) AS LONG
REGISTER i AS LONG, j AS LONG
LOCAL r AS LONG
    i = 2
    DO WHILE i * i <= n
        j = n \ i
        IF n MOD i = 0 THEN
            r += i
            IF i <> j THEN
                r += j
            END IF
        END IF
        INCR i
    LOOP
    FUNCTION = r
END FUNCTION
 
FUNCTION chowla1(BYVAL n AS QUAD) AS QUAD
LOCAL i, j, r AS QUAD
    i = 2
    DO WHILE i * i <= n
        j = n \ i
        IF n MOD i = 0 THEN
            r += i
            IF i <> j THEN
                r += j
            END IF
        END IF
        INCR i
    LOOP
    FUNCTION = r
END FUNCTION
 
SUB sieve(BYVAL limit AS LONG, BYREF c() AS INTEGER)
LOCAL i, j AS LONG
REDIM c(limit - 1)
    i = 3
    DO WHILE i * 3 < limit
        IF NOT c(i) THEN
            IF chowla(i) = 0 THEN
                j = 3 * i
                DO WHILE j < limit
                    c(j) = -1
                    j += 2 * i
                LOOP
            END IF
        END IF
        i += 2
    LOOP
END SUB
 
FUNCTION PBMAIN () AS LONG
LOCAL i, count, limit, power AS LONG
LOCAL c() AS INTEGER
LOCAL s AS STRING
LOCAL s30 AS STRING * 30
LOCAL p, k, kk, r, ql AS QUAD
    FOR i = 1 TO 37
        s = "chowla(" & TRIM$(STR$(i)) & ") = " & TRIM$(STR$(chowla(i)))
        CON.PRINT s
    NEXT i
    count = 1
    limit = 10000000
    power = 100
    CALL sieve(limit, c())
    FOR i = 3 TO limit - 1 STEP 2
        IF ISFALSE c(i) THEN count += 1
        IF i = power - 1 THEN
            RSET s30 = FORMAT$(power, "#,##0")
            s = "Count of primes up to " & s30 & " =" & STR$(count)
            CON.PRINT s
            power *= 10
        END IF
    NEXT i
 
    ql = 2 ^ 61
    k = 2: kk = 3
    RESET count
    DO
        p = k * kk : IF p > ql THEN EXIT DO
        IF chowla1(p) = p - 1 THEN
            RSET s30 = FORMAT$(p, "#,##0")
            s = s30 & " is a number that is perfect"
            CON.PRINT s
            count += 1
        END IF
        k = kk + 1 : kk += k
    LOOP
    s = "There are" & STR$(count) & " perfect numbers <= " & FORMAT$(ql, "#,##0")
    CON.PRINT s
 
    CON.PRINT "press any key to exit program"
    CON.WAITKEY$
END FUNCTION