Brazilian numbers: Difference between revisions
Dialects of BASIC moved to the BASIC section.
(Dialects of BASIC moved to the BASIC section.) |
|||
Line 439:
First 20 prime brazilian numbers:
7 13 31 43 73 127 157 211 241 307 421 463 601 757 1093 1123 1483 1723 2551 2801</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
Line 511 ⟶ 512:
first 20 prime Brazilian numbers: 7 13 31 43 73 127 157 211 241 307 421 463 601 757 1093 1123 1483 1723 2551 2801
</pre>
=={{header|BASIC}}==
==={{header|FreeBASIC}}===
{{trans|Visual Basic .NET}}
<syntaxhighlight lang="freebasic">Function sameDigits(Byval n As Integer, Byval b As Integer) As Boolean
Dim f As Integer = n Mod b : n \= b
While n > 0
If n Mod b <> f Then Return False Else n \= b
Wend
Return True
End Function
Function isBrazilian(Byval n As Integer) As Boolean
If n < 7 Then Return False
If n Mod 2 = 0 Then Return True
For b As Integer = 2 To n - 2
If sameDigits(n, b) Then Return True
Next b
Return False
End Function
Function isPrime(Byval n As Integer) As Boolean
If n < 2 Then Return False
If n Mod 2 = 0 Then Return n = 2
If n Mod 3 = 0 Then Return n = 3
Dim d As Integer = 5
While d * d <= n
If n Mod d = 0 Then Return False Else d += 2
If n Mod d = 0 Then Return False Else d += 4
Wend
Return True
End Function
Dim kind(2) As String ={"", "odd", "prime"}
For i As Integer = 0 To 2
Print Using "First 20 & Brazilian numbers: "; kind(i)
Dim Limit As Integer = 20, n As Integer = 7
Do
If isBrazilian(n) Then Print Using "& "; n; : Limit -= 1
Select Case kind(i)
Case "" : n += 1
Case "odd" : n += 2
Case "prime" : Do : n += 2 : Loop Until isPrime(n)
End Select
Loop While Limit > 0
Next i
Sleep</syntaxhighlight>
==={{header|Visual Basic .NET}}===
{{trans|C#}}
<syntaxhighlight lang="vbnet">Module Module1
Function sameDigits(ByVal n As Integer, ByVal b As Integer) As Boolean
Dim f As Integer = n Mod b : n \= b : While n > 0
If n Mod b <> f Then Return False Else n \= b
End While : Return True
End Function
Function isBrazilian(ByVal n As Integer) As Boolean
If n < 7 Then Return False
If n Mod 2 = 0 Then Return True
For b As Integer = 2 To n - 2
If sameDigits(n, b) Then Return True
Next : Return False
End Function
Function isPrime(ByVal n As Integer) As Boolean
If n < 2 Then Return False
If n Mod 2 = 0 Then Return n = 2
If n Mod 3 = 0 Then Return n = 3
Dim d As Integer = 5
While d * d <= n
If n Mod d = 0 Then Return False Else d += 2
If n Mod d = 0 Then Return False Else d += 4
End While : Return True
End Function
Sub Main(args As String())
For Each kind As String In {" ", " odd ", " prime "}
Console.WriteLine("First 20{0}Brazilian numbers:", kind)
Dim Limit As Integer = 20, n As Integer = 7
Do
If isBrazilian(n) Then Console.Write("{0} ", n) : Limit -= 1
Select Case kind
Case " " : n += 1
Case " odd " : n += 2
Case " prime " : Do : n += 2 : Loop Until isPrime(n)
End Select
Loop While Limit > 0
Console.Write(vbLf & vbLf)
Next
End Sub
End Module</syntaxhighlight>
{{out}}
<pre>First 20 Brazilian numbers:
7 8 10 12 13 14 15 16 18 20 21 22 24 26 27 28 30 31 32 33
First 20 odd Brazilian numbers:
7 13 15 21 27 31 33 35 39 43 45 51 55 57 63 65 69 73 75 77
First 20 prime Brazilian numbers:
7 13 31 43 73 127 157 211 241 307 421 463 601 757 1093 1123 1483 1723 2551 2801
</pre>
====Speedier Version====
Based on the C# speedier version, performance is just as good, one billion Brazilian numbers counted in 4 1/2 seconds (on a core i7).
<syntaxhighlight lang="vbnet">Imports System
Module Module1
' flags:
Const _
PrMk As Integer = 0, ' a number that is prime
SqMk As Integer = 1, ' a number that is the square of a prime number
UpMk As Integer = 2, ' a number that can be factored (aka un-prime)
BrMk As Integer = -2, ' a prime number that is also a Brazilian number
Excp As Integer = 121 ' exception square - the only square prime that is a Brazilian
Dim pow As Integer = 9,
max As Integer ' maximum sieve array length
' An upper limit of the required array length can be calculated Like this:
' power of 10 fraction limit actual result
' 1 2 / 1 * 10 = 20 20
' 2 4 / 3 * 100 = 133 132
' 3 6 / 5 * 1000 = 1200 1191
' 4 8 / 7 * 10000 = 11428 11364
' 5 10/ 9 * 100000 = 111111 110468
' 6 12/11 * 1000000 = 1090909 1084566
' 7 14/13 * 10000000 = 10769230 10708453
' 8 16/15 * 100000000 = 106666666 106091516
' 9 18/17 * 1000000000 = 1058823529 1053421821
' powers above 9 are impractical because of the maximum array length in VB.NET,
' which is around the UInt32.MaxValue, Or 4294967295
Dim PS As SByte() ' the prime/Brazilian number sieve
' once the sieve is populated, primes are <= 0, non-primes are > 0,
' Brazilian numbers are (< 0) or (> 1)
' 121 is a special case, in the sieve it is marked with the BrMk (-2)
' typical sieve of Eratosthenes algorithm
Sub PrimeSieve(ByVal top As Integer)
PS = New SByte(top) {} : Dim i, ii, j As Integer
i = 2 : j = 4 : PS(j) = SqMk : While j < top - 2 : j += 2 : PS(j) = UpMk : End While
i = 3 : j = 9 : PS(j) = SqMk : While j < top - 6 : j += 6 : PS(j) = UpMk : End While
i = 5 : ii = 25 : While ii < top
If PS(i) = PrMk Then
j = (top - i) / i : If (j And 1) = 0 Then j -= 1
Do : If PS(j) = PrMk Then PS(i * j) = UpMk
j -= 2 : Loop While j > i : PS(ii) = SqMk
End If
Do : i += 2 : Loop While PS(i) <> PrMk : ii = i * i
End While
End Sub
' consults the sieve and returns whether a number is Brazilian
Function IsBr(ByVal number As Integer) As Boolean
Return Math.Abs(PS(number)) > SqMk
End Function
' shows the first few Brazilian numbers of several kinds
Sub FirstFew(ByVal kind As String, ByVal amt As Integer)
Console.WriteLine(vbLf & "The first {0} {1}Brazilian Numbers are:", amt, kind)
Dim i As Integer = 7 : While amt > 0
If IsBr(i) Then amt -= 1 : Console.Write("{0} ", i)
Select Case kind : Case "odd " : i += 2
Case "prime " : Do : i += 2 : Loop While PS(i) <> BrMk OrElse i = Excp
Case Else : i += 1 : End Select : End While : Console.WriteLine()
End Sub
' expands a 111_X number into an integer
Function Expand(ByVal NumberOfOnes As Integer, ByVal Base As Integer) As Integer
Dim res As Integer = 1
While NumberOfOnes > 1 AndAlso res < Integer.MaxValue \ Base
res = res * Base + 1 : NumberOfOnes -= 1 : End While
If res > max OrElse res < 0 Then res = 0
Return res
End Function
' returns an elapsed time string
Function TS(ByVal fmt As String, ByRef st As DateTime, ByVal Optional reset As Boolean = False) As String
Dim n As DateTime = DateTime.Now,
res As String = String.Format(fmt, (n - st).TotalMilliseconds)
If reset Then st = n
Return res
End Function
Sub Main(args As String())
Dim p2 As Integer = pow << 1, primes(6) As Integer, n As Integer,
st As DateTime = DateTime.Now, st0 As DateTime = st,
p10 As Integer = CInt(Math.Pow(10, pow)), p As Integer = 10, cnt As Integer = 0
max = CInt(((CLng((p10)) * p2) / (p2 - 1))) : PrimeSieve(max)
Console.WriteLine(TS("Sieving took {0} ms", st, True))
' make short list of primes before Brazilians are added
n = 3 : For i As Integer = 0 To primes.Length - 1
primes(i) = n : Do : n += 2 : Loop While PS(n) <> 0 : Next
Console.WriteLine(vbLf & "Checking first few prime numbers of sequential ones:" &
vbLf & "ones checked found")
' now check the '111_X' style numbers. many are factorable, but some are prime,
' then re-mark the primes found in the sieve as Brazilian.
' curiously, only the numbers with a prime number of ones will turn out, so
' restricting the search to those saves time. no need to wast time on even numbers of ones,
' or 9 ones, 15 ones, etc...
For Each i As Integer In primes
Console.Write("{0,4}", i) : cnt = 0 : n = 2 : Do
If (n - 1) Mod i <> 0 Then
Dim br As Long = Expand(i, n)
If br > 0 Then
If PS(br) < UpMk Then PS(br) = BrMk : cnt += 1
Else
Console.WriteLine("{0,8}{1,6}", n, cnt) : Exit Do
End If
End If : n += 1 : Loop While True
Next
Console.WriteLine(TS("Adding Brazilian primes to the sieve took {0} ms", st, True))
For Each s As String In ",odd ,prime ".Split(",") : FirstFew(s, 20) : Next
Console.WriteLine(TS(vbLf & "Required output took {0} ms", st, True))
Console.WriteLine(vbLf & "Decade count of Brazilian numbers:")
n = 6 : cnt = 0 : Do : While cnt < p : n += 1 : If IsBr(n) Then cnt += 1
End While
Console.WriteLine("{0,15:n0}th is {1,-15:n0} {2}", cnt, n, TS("time: {0} ms", st))
If p < p10 Then p *= 10 Else Exit Do
Loop While (True) : PS = New SByte(-1) {}
Console.WriteLine(vbLf & "Total elapsed was {0} ms", (DateTime.Now - st0).TotalMilliseconds)
If System.Diagnostics.Debugger.IsAttached Then Console.ReadKey()
End Sub
End Module
</syntaxhighlight>
{{out}}
<pre>Sieving took 2967.834 ms
Checking first few prime numbers of sequential ones:
ones checked found
3 32540 3923
5 182 44
7 32 9
11 8 1
13 8 3
17 4 1
19 4 1
Adding Brazilian primes to the sieve took 8.6242 ms
The first 20 Brazilian Numbers are:
7 8 10 12 13 14 15 16 18 20 21 22 24 26 27 28 30 31 32 33
The first 20 odd Brazilian Numbers are:
7 13 15 21 27 31 33 35 39 43 45 51 55 57 63 65 69 73 75 77
The first 20 prime Brazilian Numbers are:
7 13 31 43 73 127 157 211 241 307 421 463 601 757 1093 1123 1483 1723 2551 2801
Required output took 2.8256 ms
Decade count of Brazilian numbers:
10th is 20 time: 0.0625 ms
100th is 132 time: 0.1156 ms
1,000th is 1,191 time: 0.1499 ms
10,000th is 11,364 time: 0.1986 ms
100,000th is 110,468 time: 0.4081 ms
1,000,000th is 1,084,566 time: 1.9035 ms
10,000,000th is 10,708,453 time: 15.9129 ms
100,000,000th is 106,091,516 time: 149.8814 ms
1,000,000,000th is 1,053,421,821 time: 1412.3526 ms
Total elapsed was 4391.7287 ms
</pre>
The point of utilizing a sieve is that it caches or memoizes the results. Since we are going through a long sequence of possible Brazilian numbers, it pays off to check the prime factoring in an efficient way, rather than one at a time.
=={{header|C}}==
{{trans|Go}}
Line 1,607 ⟶ 1,876:
</pre>
=={{header|Fōrmulæ}}==
Line 4,278 ⟶ 4,503:
1,000,000th Brazilian number = 1084566
</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
| |||