Pernicious numbers: Difference between revisions

← Older edit

Pernicious numbers (view source)

Revision as of 19:19, 21 February 2024

10,860 bytes added , 2 months ago

m

Added Easylang

Chkas

1,983

edits

Revision as of 16:06, 17 January 2023 (view source) Querfeld (talk \| contribs) (→‎OCaml: add) ← Older edit		Latest revision as of 19:19, 21 February 2024 (view source) Chkas (talk \| contribs) m (Added Easylang)
(13 intermediate revisions by 9 users not shown)
Line 22: =={{header\|11l}}== <syntaxhighlight lang="11l">F ~~popcount~~is_prime(n) ~~R bin(n).count(‘1’)~~ ~~F is_prime(n)~~ I n < 2 R 0B Line 36 ⟶ 33: V cnt = 0 L I is_prime(bits:popcount(i)) print(i, end' ‘ ’) cnt++ Line 45 ⟶ 42: print() L(i) 888888877..888888888 I is_prime(bits:popcount(i)) print(i, end' ‘ ’)</syntaxhighlight> Line 188 ⟶ 185: 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886 </pre> =={{header\|Action!}}== Action! integers are limited to 16 bits, so this implements 32 bit addition and multiplication by 8-bit values to handle the larger numbers. <syntaxhighlight lang="action!"> ;;; 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 </syntaxhighlight> {{out}} <pre> 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886 </pre> Line 560 ⟶ 682: 888888877 888888878 888888880 888888883 888888885 888888886 </pre> =={{header\|BASIC}}== ==={{header\|BASIC256}}=== <syntaxhighlight lang="basic">n = 1 cont = 0 print "The following are the first 25 pernicious numbers:" print do if isPernicious(n) then print rjust(string(n), 3); cont += 1 end if n += 1 until cont = 25 print : print print "The pernicious numbers between 888,888,877 and 888,888,888 inclusive are:" print for n = 888888877 to 888888888 if isPernicious(n) then print rjust(string(n), 10); next n end function SumBinaryDigits(number) if number < 0 then number = -number # convert negative numbers to positive sum = 0 while number > 0 sum += number mod 2 number /= 2 end while return sum end function function isPrime(v) if v < 2 then return False if v mod 2 = 0 then return v = 2 if v mod 3 = 0 then return v = 3 d = 5 while d * d <= v if v mod d = 0 then return False else d += 2 end while return True end function function isPernicious(number) popcont = SumBinaryDigits(number) return isPrime(popcont) end function</syntaxhighlight> {{out}} <pre>Same as FreeBASIC entry.</pre> ==={{header\|Gambas}}=== <syntaxhighlight lang="vbnet">Public Sub Main() Dim n As Integer = 1, count As Integer = 0 Print "The following are the first 25 pernicious numbers:\n" Do If isPernicious(n) Then Print Format$(n, "###"); count += 1 End If n += 1 Loop Until count = 25 Print "\n\nThe pernicious numbers between 888,888,877 and 888,888,888 inclusive are:\n" For n = 888888877 To 888888888 If isPernicious(n) Then Print Format$(n, "##########"); Next Print End Public Sub isPrime(ValorEval As Long) As Boolean If ValorEval < 2 Then Return False If ValorEval Mod 2 = 0 Then Return ValorEval = 2 If ValorEval Mod 3 = 0 Then Return ValorEval = 3 Dim d As Long = 5 While d * d <= ValorEval If ValorEval Mod d = 0 Then Return False Else d += 2 Wend Return True End Function Public Function SumBinaryDigits(number As Integer) As Integer If number < 0 Then number = -number ' convert negative numbers to positive Dim sum As Integer = 0 While number > 0 sum += number Mod 2 number \= 2 Wend Return sum End Function Public Function isPernicious(number As Integer) As Boolean Dim popCount As Integer = SumBinaryDigits(number) Return isPrime(popCount) End Function</syntaxhighlight> {{out}} <pre>Same as FreeBASIC entry.</pre> ==={{header\|Yabasic}}=== <syntaxhighlight lang="basic">n = 1 cont = 0 print "The following are the first 25 pernicious numbers:\n" repeat if isPernicious(n) then print n using ("###"); cont = cont + 1 fi n = n + 1 until cont = 25 print "\n\nThe pernicious numbers between 888,888,877 and 888,888,888 inclusive are:\n" for n = 888888877 to 888888888 if isPernicious(n) print n using("##########"); next n print end sub SumBinaryDigits(number) if number < 0 number = -number // convert negative numbers to positive sum = 0 while number > 0 sum = sum + mod(number, 2) number = int(number / 2) wend return sum end sub sub isPrime(v) if v < 2 return False if mod(v, 2) = 0 return v = 2 if mod(v, 3) = 0 return v = 3 d = 5 while d * d <= v if mod(v, d) = 0 then return False else d = d + 2 : fi wend return True end sub sub isPernicious(number) popcont = SumBinaryDigits(number) return isPrime(popcont) end sub</syntaxhighlight> {{out}} <pre>Same as FreeBASIC entry.</pre> =={{header\|Befunge}}== Line 931 ⟶ 1,209: {{Out}} <pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886</pre> =={{header\|Cowgol}}== <syntaxhighlight lang="cowgol">include "cowgol.coh"; sub prime(n: uint8): (r: uint8) is if n<2 then r := 0; return; end if; r := 1; var d: uint8 := 2; while dd <= n loop if n%d == 0 then r := 0; return; end if; d := d + 1; end loop; end sub; sub popcount(n: uint32): (count: uint8) is count := 0; while n > 0 loop count := count + (n as uint8 & 1); n := n >> 1; end loop; end sub; sub pernicious(n: uint32): (r: uint8) is r := prime(popcount(n)); end sub; var candidate: uint32 := 0; var seen: uint8 := 0; while seen < 25 loop candidate := candidate + 1; if pernicious(candidate) != 0 then print_i32(candidate); print_char(' '); seen := seen + 1; end if; end loop; print_nl(); candidate := 888888877; while candidate < 888888888 loop if pernicious(candidate) != 0 then print_i32(candidate); print_char(' '); end if; candidate := candidate + 1; end loop; print_nl();</syntaxhighlight> {{out}} <pre>3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886</pre> Line 949 ⟶ 1,285: 1_421_120_880 Pernicious numbers in the unsigned 32 bit range in less than 48 seconds with this line: <syntaxhighlight lang="d">uint.max.iota.filter!pernicious.walkLength.writeln;</syntaxhighlight> =={{header\|EasyLang}}== <syntaxhighlight> fastfunc isprim num . if num < 2 return 0 . i = 2 while i <= sqrt num if num mod i = 0 return 0 . i += 1 . return 1 . func popc n . while n > 0 r += n mod 2 n = n div 2 . return r . n = 1 while cnt < 25 if isprim popc n = 1 write n & " " cnt += 1 . n += 1 . print "" n = 1 for n = 888888877 to 888888888 if isprim popc n = 1 write n & " " . . </syntaxhighlight> {{out}} <pre> 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886 </pre> =={{header\|EchoLisp}}== Line 1,369 ⟶ 1,751: =={{header\|Fōrmulæ}}== Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition. {{FormulaeEntry\|page=https://formulae.org/?script=examples/Pernicious_numbers}} Programs in Fōrmulæ are created/edited online in its [https://formulae.org website], However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used. '''Solution''' ~~In '''[https://formulae.org/?example=Pernicious_numbers this]''' page you can see the program(s) related to this task and their results.~~ [[File:Fōrmulæ - Pernicious numbers 01.png]] '''Case 1. Display the first 25 pernicious numbers (in decimal)''' [[File:Fōrmulæ - Pernicious numbers 02.png]] [[File:Fōrmulæ - Pernicious numbers 03.png]] '''Case 2. display all pernicious numbers between 888,888,877 and 888,888,888 (inclusive).''' [[File:Fōrmulæ - Pernicious numbers 04.png]] [[File:Fōrmulæ - Pernicious numbers 05.png]] =={{header\|Go}}== Line 1,921 ⟶ 2,316: Pernicious numbers betweeen 888888877 and 888888888 inclusive <syntaxhighlight lang="mathematica">Cases[Range[888888877, 888888888], _?(perniciousQ@# &)]</syntaxhighlight> =={{header\|Miranda}}== <syntaxhighlight lang="miranda">main :: [sys_message] main = [Stdout (lay (map show [first25, large]))] first25 :: [num] first25 = take 25 (filter pernicious [1..]) large :: [num] large = filter pernicious [888888877..888888888] pernicious :: num->bool pernicious = prime . popcount popcount :: num->num popcount 0 = 0 popcount n = n mod 2 + popcount (n div 2) prime :: num->bool prime n = n >= 2 & and [n mod d ~= 0 \| d<-[2..sqrt n]] </syntaxhighlight> {{out}} <pre>[3,5,6,7,9,10,11,12,13,14,17,18,19,20,21,22,24,25,26,28,31,33,34,35,36] [888888877,888888878,888888880,888888883,888888885,888888886]</pre> =={{header\|Modula-2}}== Line 2,851 ⟶ 3,270: The first 25 pernicious numbers: 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 </pre> =={{header\|RPL}}== ≪ '''IF''' DUP 5 ≤ '''THEN''' { 2 3 5 } SWAP POS '''ELSE''' '''IF''' DUP 2 MOD NOT '''THEN''' 2 '''ELSE''' DUP √ CEIL → lim ≪ 3 '''WHILE''' DUP2 MOD OVER lim ≤ AND '''REPEAT''' 2 + '''END''' ≫ '''END''' MOD '''END''' SIGN ≫ ''''PRIM?'''' STO ≪ BIN R→B →STR 0 1 3 PICK SIZE '''FOR''' j '''IF''' OVER j DUP SUB "1" == '''THEN''' 1 + '''END NEXT''' SWAP DROP '''PRIM?''' ≫ ´'''PERN?'''’ STO ≪ { } 1 '''WHILE''' OVER SIZE 25 < '''REPEAT IF''' DUP PERN? '''THEN''' SWAP OVER + SWAP '''END''' 1 + '''END''' DROP ≫ ´'''TASK1'''’ STO ≪ { } 888888877 888888888 '''FOR''' n '''IF''' n '''PERN? THEN''' n + '''END NEXT''' ≫ ´'''TASK2'''’ STO {{out}} <pre> 2: { 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 } 1: { 888888877 888888878 888888880 888888883 888888885 888888886 } </pre> Line 3,366 ⟶ 3,816: =={{header\|Wren}}== {{trans\|Go}} <syntaxhighlight lang="~~ecmascript~~wren">var pernicious = Fn.new { \|w\| var ff = 2.pow(32) - 1 var mask1 = (ff / 3).floor Line 3,393 ⟶ 3,843: System.print()</syntaxhighlight> {{out}} <pre> 3 5 6 7 9 10 11 12 13 14 17 18 19 20 21 22 24 25 26 28 31 33 34 35 36 888888877 888888878 888888880 888888883 888888885 888888886 </pre> =={{header\|XPL0}}== <syntaxhighlight lang "XPL0">func IsPrime(N); \Return 'true' if N is prime int N, D; [if N <= 2 then return N = 2; D:= 2; while DD <= N do [if rem(N/D) = 0 then return false; D:= D+1; ]; return true; ]; func BitCount(N); \Return number of set bits in N int N, C; [C:= 0; while N do [C:= C+1; N:= N & N-1; ]; return C; ]; int N, C; [N:= 0; C:= 0; loop [if IsPrime(BitCount(N)) then [IntOut(0, N); ChOut(0, ^ ); C:= C+1; if C >= 25 then quit; ]; N:= N+1; ]; CrLf(0); for N:= 888_888_877 to 888_888_888 do if IsPrime(BitCount(N)) then [IntOut(0, N); ChOut(0, ^ )]; CrLf(0); ]</syntaxhighlight> {{out}} <pre>