115 lines
3.1 KiB
Text
115 lines
3.1 KiB
Text
;;; find some pernicious numbers - numbers where the population count is prime
|
|
|
|
;;; As the task requires 32 bit integers, this implements 32-bit unsigend
|
|
;;; integer addition and multiplication by an 8-bit integer.
|
|
;;; The 32-bit values are stored in 4 separate bytes
|
|
|
|
|
|
;;; returns the population (number of bits on) of the non-negative integer n
|
|
BYTE FUNC population( CARD n )
|
|
CARD number
|
|
BYTE result
|
|
number = n
|
|
result = 0;
|
|
WHILE number > 0 DO
|
|
IF number AND 1 THEN result ==+ 1 FI
|
|
number ==/ 2
|
|
OD
|
|
RETURN( result )
|
|
|
|
;;; returns TRUE if n is a prime; n must be <= 32
|
|
BYTE FUNC isSmallPrime( BYTE n )
|
|
BYTE result
|
|
IF n = 2 THEN result = 1
|
|
ELSEIF ( n AND 1 ) = 0 THEN result = 0
|
|
ELSEIF n = 1 OR n = 9 OR n = 15
|
|
OR n = 21 OR n = 25 OR n = 27
|
|
THEN result = 0
|
|
ELSE result = 1
|
|
FI
|
|
RETURN( result )
|
|
|
|
;;; returns TRUE if n is pernicious, FALSE otherwise
|
|
BYTE FUNC isPernicious( CARD n ) RETURN( isSmallPrime( population( n ) ) )
|
|
|
|
;;; returns TRUE if the 32 bit integer in i1, i2, i3, i4 is pernicious,
|
|
;;; FALSE otherwise
|
|
BYTE FUNC isPernicious32( BYTE i1, i2, i3, i4 )
|
|
BYTE p
|
|
p = population( i1 ) + population( i2 )
|
|
+ population( i3 ) + population( i4 )
|
|
RETURN( isSmallPrime( p ) )
|
|
|
|
;;; adds b to the 32 bit unsigned integer in i1, i2, i3 and i4
|
|
PROC i32add8( BYTE POINTER i1, i2, i3, i4, BYTE b )
|
|
CARD c1, c2, c3, c4
|
|
|
|
c1 = i1^ c2 = i2^ c3 = i3^ c4 = i4^
|
|
c4 ==+ b
|
|
i4 ^= c4 MOD 256
|
|
c3 ==+ c4 / 256
|
|
i3 ^= c3 MOD 256
|
|
c2 ==+ c3 / 256
|
|
i2 ^= c2 MOD 256
|
|
c1 ==+ c2 / 256
|
|
i1 ^= c1 MOD 256
|
|
|
|
RETURN
|
|
|
|
;;; multiplies the 32 bit unsigned integer in i1, i2, i3 and i4 by b
|
|
PROC i32mul8( BYTE POINTER i1, i2, i3, i4, BYTE b )
|
|
CARD c1, c2, c3, c4, r
|
|
|
|
c1 = i1^ c2 = i2^ c3 = i3^ c4 = i4^
|
|
|
|
r = c4 * b
|
|
i4 ^= r MOD 256
|
|
r = ( c3 * b ) + ( r / 256 )
|
|
i3 ^= r MOD 256
|
|
r = ( c2 * b ) + ( r / 256 )
|
|
i2 ^= r MOD 256
|
|
r = ( c1 * b ) + ( r / 256 )
|
|
i1 ^= r MOD 256
|
|
|
|
RETURN
|
|
|
|
;;; find the first 25 pernicious numbers
|
|
PROC Main()
|
|
BYTE perniciousCount, i
|
|
BYTE i81, i82, i83, i84
|
|
BYTE p81, p82, p83, p84
|
|
|
|
perniciousCount = 0
|
|
i = 0
|
|
WHILE perniciousCount < 25 DO
|
|
IF isPernicious( i ) THEN
|
|
; found a pernicious number
|
|
PrintB( i )Put(' )
|
|
perniciousCount ==+ 1
|
|
FI
|
|
i ==+ 1
|
|
OD
|
|
PutE()
|
|
|
|
; find the pernicious numbers between 888 888 877 and 888 888 888
|
|
|
|
; form 888 888 800 in i81, i82, i83 and i84
|
|
i81 = 0 i82 = 0 i83 = 0 i84 = 88 ; 88
|
|
i32mul8( @i81, @i82, @i83, @i84, 100 ) ; 8 800
|
|
i32add8( @i81, @i82, @i83, @i84, 88 ) ; 8 888
|
|
i32mul8( @i81, @i82, @i83, @i84, 100 ) ; 888 800
|
|
i32add8( @i81, @i82, @i83, @i84, 88 ) ; 888 888
|
|
i32mul8( @i81, @i82, @i83, @i84, 10 ) ; 8 888 880
|
|
i32add8( @i81, @i82, @i83, @i84, 8 ) ; 8 888 888
|
|
i32mul8( @i81, @i82, @i83, @i84, 100 ) ; 888 888 800
|
|
|
|
FOR i = 77 TO 88 DO
|
|
p81 = i81 p82 = i82 p83 = i83 p84 = i84
|
|
i32add8( @p81, @p82, @p83, @p84, i )
|
|
IF isPernicious32( p81, p82, p83, p84 )
|
|
THEN
|
|
print( "8888888" )PrintB( i )Put(' )
|
|
FI
|
|
OD
|
|
PutE()
|
|
RETURN
|