Multi-base primes: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(New post.) |
||
Line 436: | Line 436: | ||
5 character strings which are prime in most bases: 30 |
5 character strings which are prime in most bases: 30 |
||
50161 -> [7 8 9 13 17 18 19 20 25 28 29 30 31 33 35 36 38 39 41 42 43 44 47 48 52 55 56 59 60 62] |
50161 -> [7 8 9 13 17 18 19 20 25 28 29 30 31 33 35 36 38 39 41 42 43 44 47 48 52 55 56 59 60 62] |
||
</pre> |
|||
=={{header|Java}}== |
|||
<syntaxhighlight lang="java"> |
|||
import java.util.ArrayList; |
|||
import java.util.Arrays; |
|||
import java.util.Collections; |
|||
import java.util.List; |
|||
public final class MultibasePrimes { |
|||
public static void main(String[] aArgs) { |
|||
final int maxBase = 36; |
|||
final int maxLength = 5; |
|||
fillPrimes(maxBase, maxLength); |
|||
multibasePrimes(maxBase, maxLength); |
|||
} |
|||
private static void multibasePrimes(int aMaxBase, int aMaxLength) { |
|||
for ( int length = 1; length <= aMaxLength; length++ ) { |
|||
int maxBasesCount = 0; |
|||
List<Tuple> maxStrings = new ArrayList<Tuple>(); |
|||
List<Integer> digits = new ArrayList<Integer>(Collections.nCopies(length, 0)); |
|||
digits.set(0, 1); |
|||
List<Integer> bases = new ArrayList<Integer>(); |
|||
do { |
|||
final int maxDigit = digits.stream().max(Integer::compare).get(); |
|||
final int minBase = Math.max(2, maxDigit + 1); |
|||
if ( maxBasesCount > aMaxBase - minBase + 1 ) { |
|||
continue; |
|||
} |
|||
bases.clear(); |
|||
for ( int base = minBase; base <= aMaxBase; base++ ) { |
|||
if ( aMaxBase - base + 1 + bases.size() < maxBasesCount ) { |
|||
break; |
|||
} |
|||
int number = 0; |
|||
for ( int digit : digits ) { |
|||
number = number * base + digit; |
|||
} |
|||
if ( primes[number] ) { |
|||
bases.add(base); |
|||
} |
|||
} |
|||
if ( bases.size() > maxBasesCount ) { |
|||
maxBasesCount = bases.size(); |
|||
maxStrings.clear(); |
|||
} |
|||
if ( bases.size() == maxBasesCount ) { |
|||
maxStrings.add( new Tuple( new ArrayList<Integer>(digits), new ArrayList<Integer>(bases) ) ); |
|||
} |
|||
} while ( increment(digits, aMaxBase) ); |
|||
System.out.println(length + "-character strings which are prime in the most bases: " + maxBasesCount); |
|||
for ( Tuple tuple : maxStrings ) { |
|||
System.out.println(numberBase(tuple.first) + " -> " + tuple.second); |
|||
} |
|||
System.out.println(); |
|||
} |
|||
} |
|||
private static boolean increment(List<Integer> aDigits, int aMaxBase) { |
|||
for ( int i = aDigits.size() - 1; i >= 0; i-- ) { |
|||
if ( aDigits.get(i) + 1 != aMaxBase ) { |
|||
aDigits.set(i, aDigits.get(i) + 1); |
|||
return true; |
|||
} |
|||
aDigits.set(i, 0); |
|||
} |
|||
return false; |
|||
} |
|||
private static String numberBase(List<Integer> aList) { |
|||
final String digits = "0123456789abcdefghijklmnopqrstuvwxyz"; |
|||
StringBuilder result = new StringBuilder(); |
|||
for ( int number : aList ) { |
|||
result.append(digits.charAt(number)); |
|||
} |
|||
return result.toString(); |
|||
} |
|||
private static void fillPrimes(int aMaxBase, int aMaxLength) { |
|||
final int limit = (int) Math.pow(aMaxBase, aMaxLength); |
|||
primes = new boolean[limit + 1]; |
|||
Arrays.fill(primes, true); |
|||
primes[0] = false; |
|||
primes[1] = false; |
|||
for ( int i = 2; i < Math.sqrt(limit); i++ ) { |
|||
if ( primes[i] ) { |
|||
int j = i * i; |
|||
while ( j <= limit ) { |
|||
primes[j] = false; |
|||
j += i; |
|||
} |
|||
} |
|||
} |
|||
} |
|||
private static class Tuple { |
|||
public Tuple(List<Integer> aFirst, List<Integer> aSecond) { |
|||
first = aFirst; second = aSecond; |
|||
} |
|||
private List<Integer> first, second; |
|||
} |
|||
private static boolean[] primes; |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
1-character strings which are prime in the most bases: 34 |
|||
2 -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] |
|||
2-character strings which are prime in the most bases: 18 |
|||
21 -> [3, 5, 6, 8, 9, 11, 14, 15, 18, 20, 21, 23, 26, 29, 30, 33, 35, 36] |
|||
3-character strings which are prime in the most bases: 18 |
|||
131 -> [4, 5, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20, 23, 25, 27, 29, 30, 34] |
|||
551 -> [6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 22, 24, 25, 26, 30, 32, 35, 36] |
|||
737 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 22, 23, 24, 25, 26, 29, 30, 31, 36] |
|||
4-character strings which are prime in the most bases: 19 |
|||
1727 -> [8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36] |
|||
5347 -> [8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36] |
|||
5-character strings which are prime in the most bases: 18 |
|||
30271 -> [8, 10, 12, 13, 16, 17, 18, 20, 21, 23, 24, 25, 31, 32, 33, 34, 35, 36] |
|||
</pre> |
</pre> |
||