Rosetta Code

Honaker primes: Difference between revisions

Page Discussion

Honaker primes (view source)

Revision as of 07:48, 7 April 2024

13,628 bytes added ,  1 month ago
m
Forth performance improvement
(added RPL)
m (Forth performance improvement)
 
(10 intermediate revisions by 6 users not shown)
Line 1:
{{draft task}}
 
A Honaker prime is a prime whose digital sum is equal to the digital sum of its position in the sequence of primes.
Line 285:
 
and the 10,000th: (286,069, 4,043,749)
</pre>
 
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
using System.Collections.Generic;
using System.Linq;
 
public class HonakerPrimes
{
private static List<int> primes = new List<int>();
private static int honakerIndex = 0;
private static int primeIndex = 0;
 
public static void Main(string[] args)
{
SievePrimes(5_000_000);
 
Console.WriteLine("The first 50 Honaker primes (honaker index: prime index, prime):");
for (int i = 1; i <= 50; i++)
{
Console.Write($"{NextHonakerPrime()}{(i % 5 == 0 ? "\n" : " ")}");
}
for (int i = 51; i < 10_000; i++)
{
NextHonakerPrime();
}
Console.WriteLine();
Console.WriteLine($"The 10,000th Honaker prime is: {NextHonakerPrime()}");
}
 
private static HonakerPrime NextHonakerPrime()
{
honakerIndex++;
primeIndex++;
while (DigitalSum(primeIndex) != DigitalSum(primes[primeIndex - 1]))
{
primeIndex++;
}
return new HonakerPrime(honakerIndex, primeIndex, primes[primeIndex - 1]);
}
 
private static int DigitalSum(int number)
{
return number.ToString().Select(c => c - '0').Sum();
}
 
private static void SievePrimes(int limit)
{
primes.Add(2);
var halfLimit = (limit + 1) / 2;
bool[] composite = new bool[halfLimit];
for (int i = 1, p = 3; i < halfLimit; p += 2, i++)
{
if (!composite[i])
{
primes.Add(p);
for (int a = i + p; a < halfLimit; a += p)
{
composite[a] = true;
}
}
}
}
 
private class HonakerPrime
{
public int HonakerIndex { get; }
public int PrimeIndex { get; }
public int Prime { get; }
 
public HonakerPrime(int honakerIndex, int primeIndex, int prime)
{
HonakerIndex = honakerIndex;
PrimeIndex = primeIndex;
Prime = prime;
}
 
public override string ToString() => $"({HonakerIndex}: {PrimeIndex}, {Prime})";
}
}
</syntaxhighlight>
{{out}}
<pre>
The first 50 Honaker primes (honaker index: prime index, prime):
(1: 32, 131) (2: 56, 263) (3: 88, 457) (4: 175, 1039) (5: 176, 1049)
(6: 182, 1091) (7: 212, 1301) (8: 218, 1361) (9: 227, 1433) (10: 248, 1571)
(11: 293, 1913) (12: 295, 1933) (13: 323, 2141) (14: 331, 2221) (15: 338, 2273)
(16: 362, 2441) (17: 377, 2591) (18: 386, 2663) (19: 394, 2707) (20: 397, 2719)
(21: 398, 2729) (22: 409, 2803) (23: 439, 3067) (24: 446, 3137) (25: 457, 3229)
(26: 481, 3433) (27: 499, 3559) (28: 508, 3631) (29: 563, 4091) (30: 571, 4153)
(31: 595, 4357) (32: 599, 4397) (33: 635, 4703) (34: 637, 4723) (35: 655, 4903)
(36: 671, 5009) (37: 728, 5507) (38: 751, 5701) (39: 752, 5711) (40: 755, 5741)
(41: 761, 5801) (42: 767, 5843) (43: 779, 5927) (44: 820, 6301) (45: 821, 6311)
(46: 826, 6343) (47: 827, 6353) (48: 847, 6553) (49: 848, 6563) (50: 857, 6653)
 
The 10,000th Honaker prime is: (10000: 286069, 4043749)
 
</pre>
 
Line 354 ⟶ 453:
 
Ten thousandth: (286069, 4043749)
</pre>
 
===Without external libraries===
<syntaxhighlight lang="c++">
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
 
uint32_t honaker_index = 0;
uint32_t prime_index = 0;
std::vector<uint32_t> primes;
 
struct HonakerPrime {
uint32_t honaker_index, prime_index, prime;
 
std::string to_string() {
return "(" + std::to_string(honaker_index) + ": "
+ std::to_string(prime_index) + ", "
+ std::to_string(prime) + ")";
}
};
 
void sieve_primes(const uint32_t& limit) {
primes.emplace_back(2);
const uint32_t half_limit = ( limit + 1 ) / 2;
std::vector<bool> composite(half_limit);
for ( uint32_t i = 1, p = 3; i < half_limit; p += 2, ++i ) {
if ( ! composite[i] ) {
primes.emplace_back(p);
for ( uint32_t a = i + p; a < half_limit; a += p ) {
composite[a] = true;
}
}
}
}
 
uint32_t digital_sum(uint32_t number) {
uint32_t sum = 0;
while ( number > 0 ) {
sum += number % 10;
number /= 10;
}
return sum;
}
 
HonakerPrime nextHonakerPrime() {
honaker_index++;
prime_index++;
while ( digital_sum(prime_index) != digital_sum(primes[prime_index - 1]) ) {
prime_index++;
}
return HonakerPrime(honaker_index, prime_index, primes[prime_index - 1]);
}
 
int main() {
sieve_primes(5'000'000);
 
std::cout << "The first 50 Honaker primes (honaker index: prime index, prime):" << std::endl;
for ( uint32_t i = 1; i <= 50; ++i ) {
std::cout << std::setw(17) << nextHonakerPrime().to_string() << ( i % 5 == 0 ? "\n" : " " );
}
for ( uint32_t i = 51; i < 10'000; ++i ) {
nextHonakerPrime();
}
std::cout << "\n" << "The 10,000th Honaker prime is: " + nextHonakerPrime().to_string() << std::endl;
}
</syntaxhighlight>
{{ out }}
<pre>
The first 50 Honaker primes (honaker index: prime index, prime):
(1: 32, 131) (2: 56, 263) (3: 88, 457) (4: 175, 1039) (5: 176, 1049)
(6: 182, 1091) (7: 212, 1301) (8: 218, 1361) (9: 227, 1433) (10: 248, 1571)
(11: 293, 1913) (12: 295, 1933) (13: 323, 2141) (14: 331, 2221) (15: 338, 2273)
(16: 362, 2441) (17: 377, 2591) (18: 386, 2663) (19: 394, 2707) (20: 397, 2719)
(21: 398, 2729) (22: 409, 2803) (23: 439, 3067) (24: 446, 3137) (25: 457, 3229)
(26: 481, 3433) (27: 499, 3559) (28: 508, 3631) (29: 563, 4091) (30: 571, 4153)
(31: 595, 4357) (32: 599, 4397) (33: 635, 4703) (34: 637, 4723) (35: 655, 4903)
(36: 671, 5009) (37: 728, 5507) (38: 751, 5701) (39: 752, 5711) (40: 755, 5741)
(41: 761, 5801) (42: 767, 5843) (43: 779, 5927) (44: 820, 6301) (45: 821, 6311)
(46: 826, 6343) (47: 827, 6353) (48: 847, 6553) (49: 848, 6563) (50: 857, 6653)
 
The 10,000th Honaker prime is: (10000: 286069, 4043749)
</pre>
 
Line 486 ⟶ 669:
</pre>
 
 
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc nextprim num .
repeat
i = 2
while i <= sqrt num and num mod i <> 0
i += 1
.
until num mod i <> 0
num += 1
.
return num
.
func digsum n .
while n > 0
sum += n mod 10
n = n div 10
.
return sum
.
proc show . .
i = 1
pri = 2
while count < 50
if digsum i = digsum pri
write "(" & i & " " & pri & ") "
count += 1
.
i += 1
pri = nextprim (pri + 1)
.
.
show
</syntaxhighlight>
 
=={{header|F_Sharp|F#}}==
Line 506 ⟶ 724:
(286069, 4043749)
</pre>
 
=={{header|Factor}}==
{{works with|Factor|0.99 2022-04-03}}
Line 531 ⟶ 750:
{ 761 5801 } { 767 5843 } { 779 5927 } { 820 6301 } { 821 6311 }
{ 826 6343 } { 827 6353 } { 847 6553 } { 848 6563 } { 857 6653 }
</pre>
 
=={{header|Forth}}==
{{works with|Gforth}}
<syntaxhighlight lang="forth">5000000 constant limit
create sieve limit allot
 
: prime? ( n -- ? ) sieve + c@ 0= ;
: notprime! ( n -- ) sieve + 1 swap c! ;
 
: prime_sieve
sieve limit erase
3
begin
dup dup * limit <
while
dup prime? if
limit over dup * do
i notprime!
dup 2* +loop
then
2 +
repeat
drop ;
 
: digit_sum ( u -- u )
dup 10 < if exit then
10 /mod recurse + ;
 
: next_odd_prime ( u -- u )
begin
2 + dup prime?
until ;
 
: next_honaker_prime ( u u -- u u )
begin
swap next_odd_prime swap 1+
2dup digit_sum swap digit_sum =
until ;
 
: print_pair ( u u -- )
." (" 3 .r ." , " 4 .r ." )" ;
 
: main
prime_sieve
." First 50 Honaker primes (index, prime):" cr
3 2 0 \ prime prime-index honaker-index
begin
dup 50 <
while
-rot next_honaker_prime
2dup print_pair rot 1+
dup 5 mod 0= if cr else space then
repeat
begin
dup 10000 <
while
-rot next_honaker_prime rot 1+
repeat
drop
cr ." Ten thousandth: " print_pair ;
 
main cr bye</syntaxhighlight>
 
{{out}}
<pre>
First 50 Honaker primes (index, prime):
( 32, 131) ( 56, 263) ( 88, 457) (175, 1039) (176, 1049)
(182, 1091) (212, 1301) (218, 1361) (227, 1433) (248, 1571)
(293, 1913) (295, 1933) (323, 2141) (331, 2221) (338, 2273)
(362, 2441) (377, 2591) (386, 2663) (394, 2707) (397, 2719)
(398, 2729) (409, 2803) (439, 3067) (446, 3137) (457, 3229)
(481, 3433) (499, 3559) (508, 3631) (563, 4091) (571, 4153)
(595, 4357) (599, 4397) (635, 4703) (637, 4723) (655, 4903)
(671, 5009) (728, 5507) (751, 5701) (752, 5711) (755, 5741)
(761, 5801) (767, 5843) (779, 5927) (820, 6301) (821, 6311)
(826, 6343) (827, 6353) (847, 6553) (848, 6563) (857, 6653)
 
Ten thousandth: (286069, 4043749)
</pre>
 
Line 787 ⟶ 1,085:
</syntaxhighlight>
 
</syntaxhighlight>
Task example:<syntaxhighlight lang=J> (>: j. p:) 5 10$I.honk i.1e3
32j131 56j263 88j457 175j1039 176j1049 182j1091 212j1301 218j1361 227j1433 248j1571
Line 795 ⟶ 1,092:
761j5801 767j5843 779j5927 820j6301 821j6311 826j6343 827j6353 847j6553 848j6563 857j6653</syntaxhighlight>
Here, we test the first thousand primes to see which are prime indices of Honaker primes. Then <code>I.</code>converts the test results back to index form, and <code>5 10$I.</code> organizes those indices in 5 rows of 10 columns (discarding any extra). Finally, we use complex number notation to form pairs of the corresponding honaker index and prime.
 
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.List;
 
public final class HonakerPrimes {
 
public static void main(String[] args) {
sievePrimes(5_000_000);
System.out.println("The first 50 Honaker primes (honaker index: prime index, prime):");
for ( int i = 1; i <= 50; i++ ) {
System.out.print(String.format("%17s%s", nextHonakerPrime(), ( i % 5 == 0 ? "\n" : " " ) ));
}
for ( int i = 51; i < 10_000; i++ ) {
nextHonakerPrime();
}
System.out.println();
System.out.println("The 10,000th Honaker prime is: " + nextHonakerPrime());
}
private static HonakerPrime nextHonakerPrime() {
honakerIndex += 1;
primeIndex += 1;
while ( digitalSum(primeIndex) != digitalSum(primes.get(primeIndex - 1)) ) {
primeIndex += 1;
}
return new HonakerPrime(honakerIndex, primeIndex, primes.get(primeIndex - 1));
}
private static int digitalSum(int number) {
return String.valueOf(number).chars().map( i -> i - (int) '0' ).sum();
}
 
private static void sievePrimes(int limit) {
primes.add(2);
final int halfLimit = ( limit + 1 ) / 2;
boolean[] composite = new boolean[halfLimit];
for ( int i = 1, p = 3; i < halfLimit; p += 2, i++ ) {
if ( ! composite[i] ) {
primes.add(p);
for ( int a = i + p; a < halfLimit; a += p ) {
composite[a] = true;
}
}
}
}
private static int honakerIndex = 0;
private static int primeIndex = 0;
private static List<Integer> primes = new ArrayList<Integer>();
private static record HonakerPrime(int honakerIndex, int primeIndex, int prime) {
public String toString() {
return "(" + honakerIndex + ": " + primeIndex + ", " + prime + ")";
}
}
 
}
</syntaxhighlight>
{{ out }}
<pre>
The first 50 Honaker primes (honaker index: prime index, prime):
(1: 32, 131) (2: 56, 263) (3: 88, 457) (4: 175, 1039) (5: 176, 1049)
(6: 182, 1091) (7: 212, 1301) (8: 218, 1361) (9: 227, 1433) (10: 248, 1571)
(11: 293, 1913) (12: 295, 1933) (13: 323, 2141) (14: 331, 2221) (15: 338, 2273)
(16: 362, 2441) (17: 377, 2591) (18: 386, 2663) (19: 394, 2707) (20: 397, 2719)
(21: 398, 2729) (22: 409, 2803) (23: 439, 3067) (24: 446, 3137) (25: 457, 3229)
(26: 481, 3433) (27: 499, 3559) (28: 508, 3631) (29: 563, 4091) (30: 571, 4153)
(31: 595, 4357) (32: 599, 4397) (33: 635, 4703) (34: 637, 4723) (35: 655, 4903)
(36: 671, 5009) (37: 728, 5507) (38: 751, 5701) (39: 752, 5711) (40: 755, 5741)
(41: 761, 5801) (42: 767, 5843) (43: 779, 5927) (44: 820, 6301) (45: 821, 6311)
(46: 826, 6343) (47: 827, 6353) (48: 847, 6553) (49: 848, 6563) (50: 857, 6653)
 
The 10,000th Honaker prime is: (10000: 286069, 4043749)
</pre>
 
=={{header|jq}}==
Line 1,550 ⟶ 1,926:
(p:46 ,ind:826 ,val:6343) (p:47 ,ind:827 ,val:6353) (p:48 ,ind:847 ,val:6553)
(p:49 ,ind:848 ,val:6563) (p:50 ,ind:857 ,val:6653)</pre>
 
 
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
import scala.collection.mutable.ListBuffer
 
object HonakerPrimes {
def main(args: Array[String]): Unit = {
sievePrimes(5000000)
 
println("The first 50 Honaker primes (honaker index: prime index, prime):")
for (i <- 1 to 50) {
print(f"${nextHonakerPrime()}%17s${if (i % 5 == 0) "\n" else " "}")
}
for (i <- 51 until 10000) {
nextHonakerPrime()
}
println()
println(s"The 10,000th Honaker prime is: ${nextHonakerPrime()}")
}
 
private def nextHonakerPrime(): HonakerPrime = {
honakerIndex += 1
primeIndex += 1
while (digitalSum(primeIndex) != digitalSum(primes(primeIndex - 1))) {
primeIndex += 1
}
HonakerPrime(honakerIndex, primeIndex, primes(primeIndex - 1))
}
 
private def digitalSum(number: Int): Int = {
number.toString.map(_.asDigit).sum
}
 
private def sievePrimes(limit: Int): Unit = {
primes += 2
val halfLimit = (limit + 1) / 2
val composite = Array.fill(halfLimit)(false)
var i = 1
var p = 3
while (i < halfLimit) {
if (!composite(i)) {
primes += p
var a = i + p
while (a < halfLimit) {
composite(a) = true
a += p
}
}
i += 1
p += 2
}
}
 
private var honakerIndex = 0
private var primeIndex = 0
private val primes = ListBuffer[Int]()
 
case class HonakerPrime(honakerIndex: Int, primeIndex: Int, prime: Int) {
override def toString: String = s"($honakerIndex: $primeIndex, $prime)"
}
}
</syntaxhighlight>
{{out}}
<pre>
The first 50 Honaker primes (honaker index: prime index, prime):
(1: 32, 131) (2: 56, 263) (3: 88, 457) (4: 175, 1039) (5: 176, 1049)
(6: 182, 1091) (7: 212, 1301) (8: 218, 1361) (9: 227, 1433) (10: 248, 1571)
(11: 293, 1913) (12: 295, 1933) (13: 323, 2141) (14: 331, 2221) (15: 338, 2273)
(16: 362, 2441) (17: 377, 2591) (18: 386, 2663) (19: 394, 2707) (20: 397, 2719)
(21: 398, 2729) (22: 409, 2803) (23: 439, 3067) (24: 446, 3137) (25: 457, 3229)
(26: 481, 3433) (27: 499, 3559) (28: 508, 3631) (29: 563, 4091) (30: 571, 4153)
(31: 595, 4357) (32: 599, 4397) (33: 635, 4703) (34: 637, 4723) (35: 655, 4903)
(36: 671, 5009) (37: 728, 5507) (38: 751, 5701) (39: 752, 5711) (40: 755, 5741)
(41: 761, 5801) (42: 767, 5843) (43: 779, 5927) (44: 820, 6301) (45: 821, 6311)
(46: 826, 6343) (47: 827, 6353) (48: 847, 6553) (49: 848, 6563) (50: 857, 6653)
 
The 10,000th Honaker prime is: (10000: 286069, 4043749)
 
</pre>
 
 
=={{header|Sidef}}==
Line 1,581 ⟶ 2,039:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
import "./fmt" for Fmt
 
Simonjsaunders
1,777

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/358096...363352"