Integer Ratios and Integer Density

[Eddie W. Shore]

How Many Integers Fit the Criteria?

The program INTDENS calculates the ratio of integers to a range of integer that fit a criteria. The seven ratios that the program offers are:

1. The number of odd integers over the range of integers

2. The number of even integers over the range of integers

3. The number of integers equally divisible by N over the range of integers. The user sets the value of N.

4. The number of perfect squares over the range of integers. An integer is a perfect square when the fractional part of integer is zero. Examples are perfect squares are 1, 4, 9, 16, and 25.

5. The number of integers that begin with digit N over the range of integers. N is the digit 0-9.

6. The number of integers that are triangular numbers over the range of integers. a triangular number is an integer of the form (n * (n + 1)) / 2.

7. The number of integers that are relativity prime to N over the range of integers. An integer is relatively prime to N when the greatest common divisor between N and that integer is 1.


The program can be used for testing whether density exists with the criteria. The density, if it exists, is defined as:

limit
n → ∞ (number of integers from 0 to n-1 that fit a criteria) / (n - 1)

For example: the integer density of odd integers is 1/2, while the integer density of integers divisible by 6 is 1/6. Beware if the limit tends towards 0 as n gets large, such as the number of perfect squares or triangular numbers.


HP Prime Program: INTDENS

Code:

Code:

EXPORT INTDENS()
BEGIN
// integer density
// 2023-03-20 EWS

LOCAL A,B,C,H,I,N,lst,E;
I:=0;

// list of choices
lst:={"Odd Integers",
"Even Integers",
"Divisible by N",
"Perfect Squares",
"Begins With Digit N",
"Triangular Numbers",
"Rel. Prime to N"}; 
  
INPUT({A,B,{H,lst}},
"Integer Density",
{"LOW: ","HIGH: ","TYPE: "});  

// odd
IF H==1 THEN
FOR I FROM A TO B DO
C:=when(I MOD 2==1,1,0)+C;
END;
END;

// even
IF H==2 THEN
FOR I FROM A TO B DO
C:=when(I MOD 2==0,1,0)+C;
END;
END;

// divisible by N
IF H==3 THEN
INPUT(N,"Divisible by N","N: ");
FOR I FROM A TO B DO
C:=when(I MOD N==1,1,0)+C;
END;
END;

// perfect squares
IF H==4 THEN
FOR I FROM A TO B DO
C:=when(FP(√I)==0,1,0)+C;
END;
END;

// begins with digit N
IF H==5 THEN
INPUT(N,"Begins with digit N","N: ");
FOR I FROM A TO B DO
E:=ALOG(IP(LOG(I)));
E:=IP(I/E);
C:=when(E==N,1,0)+C;
END;
END;

// triangular numbers
IF H==6 THEN
FOR I FROM A TO B DO
E:=(−1+√(1+8*I))/2;
C:=when(FP(E)==0,1,0)+C;
END;
END;

// relatively prime to N
IF H==7 THEN
INPUT(N,"Relatively Prime to N","N: ");
FOR I FROM A TO B DO
C:=when(gcd(I,N)==1,1,0)+C;
END;
END;
 
// results
N:=B-A+1;
MSGBOX("Count: "+STRING(C)+"\n
Range: "+STRING(N)+"\n
Ratio: "+STRING(C/N)); 
RETURN QPI(C/N);  
   
END;

Examples


For this set of examples: A = 1 (low), B = 3000 (high)

Ratio of odd integers: 1/2

Ratio of even integers: 1/2

Ratio of integers divisible by 5 (N = 5): 1/5

Ratio of perfect squares: 9/500

Ratio of integers beginning with 2: 1111/3000

Ratio of triangular numbers: 19/750

Ratio of integers relatively prime to 250 (N = 250): 2/5


Source

Diaconis, Persi and Brian Skyrms Ten Great Ideas About Chance Princeton University Press: Princeton, NJ. 2018. ISBN 978-0-691-19639-8