Anonymous user
Powerful numbers: Difference between revisions
→{{header|Go}}
SqrtNegInf (talk | contribs) m (→{{header|Raku}}: Fix link: Perl 6 --> Raku) |
|||
Line 168:
Count of 9-powerful numbers <= 10^j, j in [0, 19): [1 1 1 2 6 11 16 24 38 59 94 145 217 317 453 644 919 1308 1868]
Count of 10-powerful numbers <= 10^j, j in [0, 20): [1 1 1 1 5 9 14 21 28 43 68 104 155 227 322 447 621 858 1192 1651]
</pre>
=={{header|Java}}==
<lang Java>
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class PowerfulNumbers {
public static void main(String[] args) {
System.out.printf("Task: For k = 2..10, generate the set of k-powerful numbers <= 10^k and show the first 5 and the last 5 terms, along with the length of the set%n");
for ( int k = 2 ; k <= 10 ; k++ ) {
BigInteger max = BigInteger.valueOf(10).pow(k);
List<BigInteger> powerfulNumbers = getPowerFulNumbers(max, k);
System.out.printf("There are %d %d-powerful numbers between 1 and %d. %nList: %s%n", powerfulNumbers.size(), k, max, getList(powerfulNumbers));
}
System.out.printf("%nTask: For k = 2..10, show the number of k-powerful numbers less than or equal to 10^j, for 0 <= j < k+10%n");
for ( int k = 2 ; k <= 10 ; k++ ) {
List<Integer> powCount = new ArrayList<>();
for ( int j = 0 ; j < k+10 ; j++ ) {
BigInteger max = BigInteger.valueOf(10).pow(j);
powCount.add(countPowerFulNumbers(max, k));
}
System.out.printf("Count of %2d-powerful numbers <= 10^j, j in [0, %d]: %s%n", k, k+9, powCount);
}
}
private static String getList(List<BigInteger> list) {
StringBuilder sb = new StringBuilder();
sb.append(list.subList(0, 5).toString().replace("]", ""));
sb.append(" ... ");
sb.append(list.subList(list.size()-5, list.size()).toString().replace("[", ""));
return sb.toString();
}
private static int countPowerFulNumbers(BigInteger max, int k) {
return potentialPowerful(max, k).size();
}
private static List<BigInteger> getPowerFulNumbers(BigInteger max, int k) {
List<BigInteger> powerfulNumbers = new ArrayList<>(potentialPowerful(max, k));
Collections.sort(powerfulNumbers);
return powerfulNumbers;
}
private static Set<BigInteger> potentialPowerful(BigInteger max, int k) {
// Setup
int[] indexes = new int[k];
for ( int i = 0 ; i < k ; i++ ) {
indexes[i] = 1;
}
Set<BigInteger> powerful = new HashSet<>();
boolean foundPower = true;
while ( foundPower ) {
boolean genPowerful = false;
for ( int index = 0 ; index < k ; index++ ) {
BigInteger power = BigInteger.ONE;
for ( int i = 0 ; i < k ; i++ ) {
power = power.multiply(BigInteger.valueOf(indexes[i]).pow(k+i));
}
if ( power.compareTo(max) <= 0 ) {
powerful.add(power);
indexes[0] += 1;
genPowerful = true;
break;
}
else {
indexes[index] = 1;
if ( index < k-1 ) {
indexes[index+1] += 1;
}
}
}
if ( ! genPowerful ) {
foundPower = false;
}
}
return powerful;
}
}
</lang>
{{out}}
<pre>
Task: For k = 2..10, generate the set of k-powerful numbers <= 10^k and show the first 5 and the last 5 terms, along with the length of the set
There are 14 2-powerful numbers between 1 and 100.
List: [1, 4, 8, 9, 16 ... 49, 64, 72, 81, 100]
There are 20 3-powerful numbers between 1 and 1000.
List: [1, 8, 16, 27, 32 ... 625, 648, 729, 864, 1000]
There are 25 4-powerful numbers between 1 and 10000.
List: [1, 16, 32, 64, 81 ... 5184, 6561, 7776, 8192, 10000]
There are 32 5-powerful numbers between 1 and 100000.
List: [1, 32, 64, 128, 243 ... 65536, 69984, 78125, 93312, 100000]
There are 38 6-powerful numbers between 1 and 1000000.
List: [1, 64, 128, 256, 512 ... 559872, 746496, 823543, 839808, 1000000]
There are 46 7-powerful numbers between 1 and 10000000.
List: [1, 128, 256, 512, 1024 ... 7558272, 8388608, 8957952, 9765625, 10000000]
There are 52 8-powerful numbers between 1 and 100000000.
List: [1, 256, 512, 1024, 2048 ... 60466176, 67108864, 80621568, 90699264, 100000000]
There are 59 9-powerful numbers between 1 and 1000000000.
List: [1, 512, 1024, 2048, 4096 ... 644972544, 725594112, 816293376, 967458816, 1000000000]
There are 68 10-powerful numbers between 1 and 10000000000.
List: [1, 1024, 2048, 4096, 8192 ... 7739670528, 8589934592, 8707129344, 9795520512, 10000000000]
Task: For k = 2..10, show the number of k-powerful numbers less than or equal to 10^j, for 0 <= j < k+10
Count of 2-powerful numbers <= 10^j, j in [0, 11]: [1, 4, 14, 54, 185, 619, 2027, 6553, 21044, 67231, 214122, 680330]
Count of 3-powerful numbers <= 10^j, j in [0, 12]: [1, 2, 7, 20, 51, 129, 307, 713, 1645, 3721, 8348, 18589, 41136]
Count of 4-powerful numbers <= 10^j, j in [0, 13]: [1, 1, 5, 11, 25, 57, 117, 235, 464, 906, 1741, 3312, 6236, 11654]
Count of 5-powerful numbers <= 10^j, j in [0, 14]: [1, 1, 3, 8, 16, 32, 63, 117, 211, 375, 659, 1153, 2000, 3402, 5770]
Count of 6-powerful numbers <= 10^j, j in [0, 15]: [1, 1, 2, 6, 12, 21, 38, 70, 121, 206, 335, 551, 900, 1451, 2326, 3706]
Count of 7-powerful numbers <= 10^j, j in [0, 16]: [1, 1, 1, 4, 10, 16, 26, 46, 77, 129, 204, 318, 495, 761, 1172, 1799, 2740]
Count of 8-powerful numbers <= 10^j, j in [0, 17]: [1, 1, 1, 3, 8, 13, 19, 32, 52, 85, 135, 211, 315, 467, 689, 1016, 1496, 2191]
Count of 9-powerful numbers <= 10^j, j in [0, 18]: [1, 1, 1, 2, 6, 11, 16, 24, 38, 59, 94, 145, 217, 317, 453, 644, 919, 1308, 1868]
Count of 10-powerful numbers <= 10^j, j in [0, 19]: [1, 1, 1, 1, 5, 9, 14, 21, 28, 43, 68, 104, 155, 227, 322, 447, 621, 858, 1192, 1651]
</pre>
| |||