challenge - prime numbers where sum of squared digits of prime number is also prime

[Gene]

Thought I would see what this looked like.

1) Find the first prime number - ok, this is 2
2) Compute the sum of the squared digits of that prime number
3) Determine if the computed sum is also prime and display it
4) Find the next prime number
5) Goto 2


For example, 11 is the first prime where the sum of its digits squared is also prime (2).
What is the next prime where this is true?
How many primes less than 1000 is this true for?
What is the largest prime less than 100,000 where this is true?

Just for curiosity. Enjoy.

[SlideRule]

from a well know wiki

Code:

A happy prime is a number that is both happy and prime. The happy primes below 500 are

7, 13, 19, 23, 31, 79, 97, 103, 109, 139, 167, 193, 239, 263, 293, 313, 331, 367, 379, 383, 397, 409, 487 (sequence A035497 in the OEIS).

All numbers, and therefore all primes, of the form 10n + 3 or 10n + 9 for n greater than 0 are happy. This does not mean that these are the only happy primes, as evidenced by the sequence above. To see this, note that

All such numbers will have at least two digits;
The first digit will always be 1 due to the 10n
The last digit will always be either 3 or 9.
Any other digits will always be 0 (and therefore will not contribute to the sum of squares of the digits).
The sequence for numbers ending in 3 is: 12 + 32 = 10 → 12 = 1.
The sequence for numbers ending in 9 is: 12 + 92 = 82 → 82 + 22 = 64 + 4 = 68 → 62 + 82 = 36 + 64 = 100 -> 1.
The palindromic prime 10150006 + 7426247×1075000 + 1 is also a happy prime with 150,007 digits because the many 0's do not contribute to the sum of squared digits, and {\displaystyle 1^{2}+7^{2}+4^{2}+2^{2}+6^{2}+2^{2}+4^{2}+7^{2}+1^{2}=176} 1^{2}+7^{2}+4^{2}+2^{2}+6^{2}+2^{2}+4^{2}+7^{2}+1^{2}=176, which is a happy number. Paul Jobling discovered the prime in 2005.[6]

As of 2010, the largest known happy prime is {\displaystyle 2^{42643801}-1} 2^{{42643801}}-1 (Mersenne prime).[dubious – discuss] Its decimal expansion has 12,837,064 digits.[7]


It is to be noted that unlike happy numbers, it cannot be assumed that rearranging the digits of a happy prime will create another happy prime. For instance using the happy prime 19 we cannot assume 91 is a happy prime. 91 being not prime !

BEST!
SlideRule

ps: the ellipsis is needed for character length; 87 max, 89 generated

[Didier Lachieze]

A quick HP Prime program providing the prime numbers between N & M fitting the requirement:

Code:

EXPORT PrCh(N,M)
BEGIN
  LOCAL n:=N-1,res:={};
  WHILE n<M DO
    n:=nextprime(n);
    IF isprime(ΣLIST((ASC(STRING(n))-48)^2)) THEN PRINT(n); res(0):=n; END;
  END;
  RETURN res;
END;

Call it with e.g. SIZE(PrCh(1,1000)) to know for how many primes less than 1000 the sum of squared digits of the number is prime.

[Gene]

(01-05-2018 02:01 PM)SlideRule Wrote:  A happy prime is a number that is both happy and prime. The happy primes below 500 are

7, 13, 19, 23, 31, 79, 97, 103, 109, 139, 167, 193, 239, 263, 293, 313, 331, 367, 379, 383, 397, 409, 487 (sequence A035497 in the OEIS).

BEST!
SlideRule

Hi!

Happy PRIMES do not fit what I had asked about. The prime 13 is happy per the list above, but although 13 is prime, 1^2 + 3^2 is 10, which is not prime.

?

[TheKaneB]

Yup, the "happy number" refers to an entire sequence:

Quote:For example, 19 is happy, as the associated sequence is:

1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1.

At the end of the sequence you must meet the number 1 (one). So it's related to, but different from, the question from the OP

[Gene]

Agreed... the Happy / Unhappy number process was used for the programming contest at this past year's HHC meeting.

Here, I'm wondering how many prime numbers have primes as the result of squaring then summing the original prime number's digits. :-)

[Didier Lachieze]

(01-05-2018 04:38 PM)Mike (Stgt) Wrote:  

(01-05-2018 01:34 PM)Gene Wrote:  How many primes less than 1000 is this true for?

49

Interesting, my program above returns 53 prime numbers below 1000, from 11 to 997:

{11,23,41,61,83,101,113,131,137,173,179,191,197,199,223,229,311,313,317,331,337,​353,373,379,397,401,409,443,449,461,463,467,601,641,643,647,661,683,719,733,739,​773,797,829,863,883,911,919,937,971,977,991,997}

[Terje Vallestad]

(01-05-2018 04:54 PM)Didier Lachieze Wrote:  

(01-05-2018 04:38 PM)Mike (Stgt) Wrote:  49

Interesting, my program above returns 53 prime numbers below 1000, from 11 to 997:

{11,23,41,61,83,101,113,131,137,173,179,191,197,199,223,229,311,313,317,331,337,​353,373,379,397,401,409,443,449,461,463,467,601,641,643,647,661,683,719,733,739,​773,797,829,863,883,911,919,937,971,977,991,997}

I think you will only get those results of you have set the calculator at Fix 0 or the Standard number setting due to the ASC(STRING ()) sequence.

Cheers, Terje

[Didier Lachieze]

(01-05-2018 06:18 PM)Terje Vallestad Wrote:  I think you will only get those results of you have set the calculator at Fix 0 or the Standard number setting due to the ASC(STRING ()) sequence.

You're right, ASC(STRING (n)) should be replaced by ASC(STRING(n,1)) to work with all number formats.

Here is the updated code, including also a fix for the WHILE exit condition:

Code:

EXPORT PrCh(N,M)
BEGIN
  LOCAL n:=N-1,res:={};
  WHILE (n:=nextprime(n))<M DO
    IF isprime(ΣLIST((ASC(STRING(n,1))-48)^2)) THEN PRINT(n); res(0):=n; END;
  END;
  RETURN res;
END;

[Gilles59]

User RPL with ListExt Library (https://www.hpcalc.org/details/7971) :

Code:

 {} 1
 WHILE DUP 1000 < REPEAT
  NEXTPRIME DUP I->NL SQ LSUM ISPRIME? {SWAP OVER + SWAP} IFT
 END
 DROP

same results as Didier

"What is the largest prime less than 100,000 where this is true?"

Code:

 100000
 DO 
  PREVPRIME 
 UNTIL DUP I->NL SQ LSUM ISPRIME? END

-> 99971

For 1'000'000'000 -> 999'999'667

[DavidM]

(01-05-2018 08:37 PM)Gilles59 Wrote:  

Code:

 {} 1
 WHILE DUP 1000 < REPEAT
  NEXTPRIME DUP I->NL SQ LSUM ISPRIME? {SWAP OVER + SWAP} IFT
 END
 DROP

Code:

 100000
 DO 
  PREVPRIME 
 UNTIL DUP I->NL SQ LSUM ISPRIME? END

Warms my heart, Gilles.

I'm starting to think of I→NL as the "challenge and puzzle" command, as it seems to be most useful in those situations.

"If the shoe fits..."

[wawa]

Here is my program for the DM42/Free42/HP42s.
The DM42 gives the answer for 100000 in 4 minutes.
Type the limit in X, the program CHALNG returns the number of such primes in X and the last prime found with that property in Y.
Ex: 100000 -> X:1818 and Y: 99971
1000 -> X:53 and Y:997

Edit : On the true hp42s, the 1000 chalenge takes 8 minutes to complete. The 100000 is out of reach in a reasonable time.

Code:

00 { 239-Byte Prgm }
01▸LBL "PR?"
02 ENTER
03 ENTER
04 ENTER
05 2
06 MOD
07 X=0?
08 GTO 02
09 CLX
10 3
11 MOD
12 X=0?
13 GTO 02
14 CLX
15 5
16 MOD
17 X=0?
18 GTO 02
19 SIGN
20 SIGN
21▸LBL 01
22 X<> ST L
23 6
24 +
25 MOD
26 X=0?
27 GTO 02
28 X<> ST L
29 4
30 +
31 MOD
32 X=0?
33 GTO 02
34 X<> ST L
35 2
36 +
37 MOD
38 X=0?
39 GTO 02
40 X<> ST L
41 4
42 +
43 MOD
44 X=0?
45 GTO 02
46 X<> ST L
47 2
48 +
49 MOD
50 X=0?
51 GTO 02
52 X<> ST L
53 4
54 +
55 MOD
56 X=0?
57 GTO 02
58 X<> ST L
59 6
60 +
61 MOD
62 X=0?
63 GTO 02
64 X<> ST L
65 2
66 +
67 MOD
68 X=0?
69 GTO 02
70 X<> ST L
71 X↑2
72 X<Y?
73 GTO 01
74 R↓
75 SIGN
76▸LBL 02
77 CLX
78 LASTX
79 X<Y?
80 CLX
81 X=Y?
82 SIGN
83 END
84▸LBL "NPRM"
85 STO 06
86 2
87 X>Y?
88 RTN
89 MOD
90 X=0?
91 DSE 06
92▸LBL 01
93 RCL 06
94 2
95 +
96 STO 06
97 XEQ "PR?"
98 X=0?
99 GTO 01
100 RCL 06
101 END
102▸LBL "CHALNG"
103 STO 03
104 0
105 STO 02
106 STO 01
107 2
108▸LBL 00
109 STO 00
110 RCL 03
111 X<Y?
112 GTO 01
113 R↓
114 XEQ A
115 XEQ "PR?"
116 X=0?
117 GTO 02
118 VIEW 00
119 RCL 00
120 STO 02
121 ISG 01
122▸LBL 02
123 RCL 00
124 XEQ "NPRM"
125 GTO 00
126▸LBL 01
127 RCL 02
128 RCL 01
129 RTN
130▸LBL A
131 0
132 X<>Y
133▸LBL 10
134 RCL ST X
135 10
136 MOD
137 X↑2
138 STO+ ST Z
139 R↓
140 10
141 ÷
142 IP
143 X≠0?
144 GTO 10
145 X<>Y
146 RTN
147 END

[pier4r]

(01-06-2018 02:18 AM)DavidM Wrote:  I'm starting to think of I→NL as the "challenge and puzzle" command, as it seems to be most useful in those situations.

I think that I->NL and the reverse command are helpful a lot if one plays with the digits of a number. The other way is to use string conversion.

[Juan14]

This program takes an integer from level 1: in the stack and returns the prime that satisfies the condition of the challenge in level 2: and the value of the sum of the digits of the prime squared in level 1:, if flag 1 is set, the prime will be the previous prime or else the next prime. The program is stored in a variable called SDIP.

«
WHILE
1 FS? { PREVPRIME } { NEXTPRIME } IFTE
{0} OVER →STR
WHILE DUP UNROT HEAD OBJ→ + SWAP TAIL DUP SIZE
REPEAT END DROP SQ ΣLIST DUP ISPRIME? NOT
REPEAT
DROP
END
»
SDIP [STO]

running the program with flag 1 cleared and 2 on level 1: we have:

2: 11
1: 2

deleting 2 from level 1: and running the program again we have:

2: 23
1: 13

To see how many of such primes are that are less than 1000, we create a little program

«
0 1000 1 SF @ SDIP will look for the previous prime
WHILE DUP 11 >
REPEAT
SDIP DROP SWAP 1 + SWAP
END DROP
»

running this program we have:

1: 53

To find the largest of such primes less than 100,000 we set flag 1 and run the program with 100000 in level 1:, we have:

2: 99971
1: 293

[Valentin Albillo]

Hi, Gene:

Just saw this challenge you posted and decided to give it a try on my trusty HP-71B plus JPC ROM emulator.

Quote:What is the next prime where this is true?

This 109-byte, 3-liner will print all elements up to a given limit:

1 INPUT Z @ N=2 @ LOOP @ N=FPRIM(N+1) @ IF N>Z THEN DISP @ END ELSE M=N @ S=0
2 REPEAT @ S=S+MOD(M,10)^2 @ M=M DIV 10 @ UNTIL NOT M @ IF NOT PRIM(S) THEN DISP N;
3 END LOOP

>RUN

? 1000

11 23 41 61 83 101 113 131 137 173 179 191 197 199 223 229 311
313 317 331 337 353 373 379 397 401 409 443 449 461 463 467 601
641 643 647 661 683 719 733 739 773 797 829 863 883 911 919 937
971 977 991 997

>RUN

? 10000

11 23 41 61 83 101 113 131 137 173 179 191 197 199 223 229 311
313 317 331 337 353 373 379 397 401 409 443 449 461 463 467 601
641 643 647 661 683 719 733 739 773 797 829 863 883 911 919 937
971 977 991 997 1013 1019 1031 1033 1091 1097 1103 1109 1163 1181
1277 1301 1303 1307 1361 1439 1451 1471 1493 1499 1613 1693 1697 16
99 1709 1741 1787 1811 1877 1901 1907 1949 2003 2029 2089 2111 2203
2221 2281 2333 2339 2393 2441 2557 2683 2777 2887 3011 3037 3079
3169 3253 3301 3307 3323 3329 3343 3347 3389 3433 3491 3583 3637 36
59 3673 3691 3701 3709 3853 3907 3923 4001 4049 4111 4139 4241 4337
4373 4391 4409 4421 4447 4481 4603 4649 4663 4733 4799 4919 4931
5059 5233 5303 5323 5477 5503 5527 5569 5639 5659 5693 5839 5857 60
43 6047 6089 6113 6131 6197 6199 6269 6311 6337 6353 6359 6373 6449
6599 6661 6719 6733 6791 6803 6823 6883 6917 6959 6971 6991 7013
7019 7039 7079 7103 7109 7127 7187 7307 7309 7411 7433 7457 7477 74
99 7547 7691 7703 7727 7817 7877 7901 7907 7949 8069 8111 8209 8221
8263 8287 8353 8539 8599 8609 8623 8803 8863 8887 8933 8999 9011
9091 9109 9323 9341 9413 9419 9431 9479 9491 9497 9613 9619 9631 97
49 9833 9859 9901 9907 9941

>RUN

? 100000

11 23 41 61 83 101 113 131 137 173 179 191 197 199 223 229 311
313 317 331 337 353 373 379 397 401 409 443 449 461 463 467 601
... ... ...
98369 98411 98639 98909 98929 98963 99041 99089 99131 99133 99223 992
89 99377 99401 99559 99623 99643 99667 99719 99733 99809 99823 99829
99971

Quote:How many primes less than 1000 is this true for?

This 110-byte, 2-liner variation will give the number of elements up to a given limit:

1 INPUT Z @ C=0 @ N=2 @ LOOP @ N=FPRIM(N+1) @ IF N>Z THEN DISP C @ END ELSE M=N @ S=0
2 REPEAT @ S=S+MOD(M,10)^2 @ M=M DIV 10 @ UNTIL NOT M @ C=C+NOT PRIM(S) @ END LOOP

>RUN

? 1000

53

>RUN

? 10000

242

>RUN

? 100000

1818

>RUN

? 1000000

14731

> RUN

? 10000000

120495

>RUN

? 100000000

1021095

>RUN

? 1000000000

8736877

I've been unable to find the last three or four values above on the net so if someone can confirm their correctness I'd be grateful.

Quote:What is the largest prime less than 100,000 where this is true?

This 84-byte, 2-liner variation will do (and provide the prime sum as well):

1 INPUT N @ REPEAT @ N=FPRIM(N-1,2) @ M=N @ S=0 @ REPEAT
2 S=S+MOD(M,10)^2 @ M=M DIV 10 @ UNTIL NOT M @ UNTIL NOT PRIM(S) @ DISP N;S

>RUN

? 1E5

99971 293

>RUN

? 1E9

999999667 607

>RUN

? 1E12

999999999767 863

Thanks for the interesting challenge and best regards.
V.
.

[Valentin Albillo]

.
Hi, Mike

(01-08-2018 09:55 PM)Mike (Stgt) Wrote:  

(01-08-2018 07:43 PM)Valentin Albillo Wrote:  This 109-byte, 3-liner will print all elements up to a given limit:

1 INPUT Z @ N=2 @ LOOP @ N=FPRIM(N+1) @ IF N>Z THEN DISP @ END ELSE M=N @ S=0
2 REPEAT @ S=S+MOD(M,10)^2 @ M=M DIV 10 @ UNTIL NOT M @ IF NOT PRIM(S) THEN DISP N;
3 END LOOP

Sorry, I get an ERR L1:Unordered at clause IF N>Z THEN DISP @

Your N and/or Z variables are presently declared as COMPLEX. Execute a DESTROY ALL statement and rerun my program.

Quote:IMHO, if N>Z we're done.

Of course we are, that's why my routine next does a DISP to close the ongoing output line, then does an END to actually end execution.

Regards.
V.
.

[Valentin Albillo]

Hi again, Mike:

Quote:So I may not confirm your last value yet.

Well, here's hoping you'll eventually succeed. In any case thanks a lot for trying.

Regards.
V.
.

[Dwight Sturrock]

Program for the HP 12C

88 steps, uses 8 storage registers, must begin with the number 3 in the x register.

Calculates the primes as requested up to 4 places- HP 12C. Program ran for 3min 35 secs to calculate up to 997. Will display the prime sum of the squares followed by the prime from which it is derived.

[/php]


STO 0
SQRT
INTG
STO 1
RCL 0
RCL 1
/
FRAC
X=0
GTO 19
1
STO -1
RCL 1
X<=Y
GTO 17
GTO 05
RCL 0
GTO 23
2
STO +0
RCL 0
GTO 01
EE
3
/
INTG
STO 2
LST x
X<>Y
-
EE
1
*
INTG
STO 3
LST x
X<>Y
-
EE
1
*
INTG
STO 4
LST x
X<>Y
-
EE
1
*
INTG
STO 5
RCL 2 //SQUARE EACH DIGIT AND SUM
2
Y^X
RCL 3
2
Y^X
+
RCL 4
2
Y^X
+
RCL 5
2
Y^X
+
STO 6 //PRIME TEST
SQRT
INTG
STO 1
RCL 6
RCL 1
/
FRAC
X=0
GTO 19
1
STO -1
RCL 1
X<=Y
GTO 83
GTO 71
RCL 6
PSE
RCL 0
PSE
GTO 19
[php]