Multi-base primes: Difference between revisions
New post.
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(New post.) |
||
Line 436:
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]
</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>
| |||