Brainsteem Compute #3 Prize Computational Maths Puzzle [Win 40% and 10% in SBD] by rycharde

mathematics · @rycharde · Jul 3 '17

$2.34

Brainsteem Compute #3 Prize Computational Maths Puzzle [Win 40% and 10% in SBD]

Problem #3 is slightly different in that it is more of a research project, perhaps even a collaborative effort. The reason for this is that I'm proposing a question to which I don't know the answer!

We expect a quizmaster to know everything, but a research proposal? Well, it could be brilliant, it might be inconclusive or it might be impossible to compute. So let's find out.


<center>http://i.imgur.com/4bNV5lM.jpg?1</center>

<hr>

<h2>The Background</h2>

Firstly, you must read [Brainsteem Compute #2](https://steemit.com/math/@rycharde/brainsteem-compute-2-prize-computational-maths-puzzle-win-40-and-10-in-sbd) as it has all the background to this question. The standard literature talks about left-truncatable and right-truncatable prime numbers. 

I prefer the term *nested primes* as, in this case, we are going to look at mixing the two algorithms together. It is also easier to think of this as building up the prime from a single digit, rather than step-wise truncating the final answer down to the starting prime.



<h2>The Question</h2>


<h3>Find the largest possible prime number that can be generated by starting with a single-digit prime and adding digits to either the RIGHT or to the LEFT of each prime, so that each number in the sequence is a prime number.</h3>


<h3>We shall exclude zeros, so that we cannot have the sequence: (3, 13, 013, 1013, ...) One example of the start of a sequence is: (3, 13, 137, 2137, 62137, ...) </h3>

For the First Prize, please include a valid method, algorithm or post the code and output. If this sequence is infinite, then try to prove that it is so.

If two different people get each of A and B correct, I shall split the First Prize. All others can participate so long as you have done or attempted either A or B.

Remember that even if you are not the first to post, this remains a learning experience that can help in future Brainsteem challenges.


<hr>

<h2>Prizes</h2>

To qualify you must upvote this post and write the answer in a comment.

To win First Prize you must include the answer *and* a valid method.

<h3>The *First Prize will be 40%* of the earnings generated by this post, paid in SBD.</h3>

The *Second Prize will be 10%* of the earnings generated by this post, awarded to *any other* correct answer in the comments section, chosen at random and paid in SBD.

<h3>Also remember that your upvote generates curation *rewards for you* and that 25% of all earnings are given to upvoters.</h3>

Prizes will be awarded after the 7 days have expired. Winners will be announced in the comments below after the draw.

The Prizes will increase with more participation and as the earnings increase.

The main thing is to enjoy the challenge and maybe learn something new.

---

Come and check out other challenges currently live!

[Brainsteem #9 Prize Maths Puzzle [Win 40% and 10% in SBD]](https://steemit.com/mathematics/@rycharde/brainsteem-9-prize-maths-puzzle-win-40-and-10-in-sbd)

[Brainsteem Compute #2 Prize Computational Maths Puzzle [Win 40% and 10% in SBD]](https://steemit.com/math/@rycharde/brainsteem-compute-2-prize-computational-maths-puzzle-win-40-and-10-in-sbd)

[Brainsteem Quickfire Q4 [Win 40% and 10% in SBD]](https://steemit.com/mathematics/@rycharde/brainsteem-quickfire-q4-win-40-and-10-in-sbd)

[Brainsteem Compute #1 Prize Computational Maths Puzzle [Win 40% and 10% in SBD]](https://steemit.com/mathematics/@rycharde/brainsteem-compute-1-prize-computational-maths-puzzle-win-40-and-10-in-sbd)

[Brainsteem #8 Prize Maths Puzzle [Win 2SBD+1SBD]](https://steemit.com/mathematics/@rycharde/brainsteem-8-prize-maths-puzzle-win-2sbd1sbd)

[Science Cryptic Crossword SCX1 [Win 10 SBD Prize]](https://steemit.com/contest/@rycharde/science-cryptic-crossword-scx1-win-10-sbd-prize)

[Brainsteem #7 Prize Maths Puzzle [Win 2SBD+1SBD]](https://steemit.com/mathematics/@rycharde/brainsteem-7-prize-maths-puzzle-win-2sbd1sbd)


---

Please upvote, resteem and follow @rycharde for more Brainsteems!
I am experimenting with tags, so the easiest way to see all Brainsteems is to follow me. Thanks.

And don't forget to upvote each other's comments to bring cheer to the whole community!

👍 pharesim, xeldal, minnowsupport, cub1, cryptoctopus, remlaps1, cmp2020, math-trail, jesta, rycharde, happychau123, oceancoinz, thinkit, mathworksheets, pipertomcat, elguille, lisa.palmer, dudiland, smithmadu, shawnfishbit, raymondspeaks, cheapogroovo, banjo, hitmeasap, marcusxman, kralizec, ausbitbot, choogirl, diana.catherine, jhermanbeans, heretickitten, pomperipossa, gindor, lenscape, arjane, redpill, stuntworks, starrkravenmaf, cloh76, flaminghedge, gpenco, fronttowardenemy, dahaz159, worldtraveler, mrwanderlust, taica, whatamidoing, numpypython, qwasert, gbenga, singa, glex, abcdoctor, jhagi.bhai, gre3n

properties (23)vote details (55)

voter	rshares	pct
xeldal	62,714,168,725	0.04%
pharesim	104,047,165,752	0.02%
cryptoctopus	33,946,791,190	0.1%
dahaz159	149,531,004	0.1%
hitmeasap	479,940,525	1%
pipertomcat	2,688,780,504	100%
cloh76	189,050,123	0.2%
jesta	8,238,451,305	0.1%
diana.catherine	405,118,736	0.1%
raymondspeaks	733,053,376	1%
cmp2020	13,600,254,431	19%
elguille	2,286,420,842	100%
heretickitten	351,965,945	0.2%
kralizec	431,823,520	0.5%
jhermanbeans	377,926,721	0.1%
worldtraveler	137,702,394	0.2%
remlaps1	14,440,240,455	19%
cub1	39,993,276,605	19%
starrkravenmaf	225,429,243	0.3%
gre3n	53,172,598	0.1%
mathworksheets	3,022,075,566	21%
pomperipossa	301,558,649	0.1%
lisa.palmer	1,437,968,351	19%
banjo	517,896,013	7.14%
fronttowardenemy	171,373,880	0.1%
gbenga	76,696,975	1%
singa	75,841,018	0.1%
numpypython	104,941,294	0.1%
arjane	250,355,646	1%
choogirl	419,373,790	0.2%
cheapogroovo	643,700,453	100%
jhagi.bhai	55,177,186	0.2%
redpill	242,883,066	1%
marcusxman	461,644,273	1%
gindor	266,406,327	0.2%
abcdoctor	69,505,975	1%
whatamidoing	110,759,831	0.1%
shawnfishbit	797,622,777	0.1%
qwasert	91,540,919	0.2%
taica	130,037,469	0.1%
happychau123	6,830,808,947	100%
rycharde	7,655,446,090	100%
oceancoinz	4,942,166,186	1%
mrwanderlust	131,506,279	0.1%
minnowsupport	52,162,633,739	1%
math-trail	13,325,499,520	100%
lenscape	258,402,061	1%
stuntworks	238,037,157	0.2%
ausbitbot	422,742,336	0.1%
gpenco	172,124,474	0.1%
flaminghedge	177,316,448	1%
thinkit	4,307,306,809	100%
smithmadu	1,021,913,119	100%
glex	71,531,757	0.1%
dudiland	1,152,418,572	100%

@minnowsupport · Jul 3 '17

$0.05

<p>Congratulations!  This post has been upvoted from the communal account, @minnowsupport, by rycharde from the Minnow Support Project.  It's a witness project run by aggroed, ausbitbank, teamsteem, theprophet0, and someguy123.  The goal is to help Steemit grow by supporting Minnows and creating a social network.  Please find us in the <a href="https://discord.gg/HYj4yvw">Peace, Abundance, and Liberty Network (PALnet) Discord Channel</a>.  It's a completely public and open space to all members of the Steemit community who voluntarily choose to be there.</p>

<p>If you like what we're doing please upvote this comment so we can continue to build the community account that's supporting all members.</p>

👍 rycharde

`post_id`	6,022,889
`author`	minnowsupport
`permlink`	re-rycharde-brainsteem-compute-3-prize-computational-maths-puzzle-win-40-and-10-in-sbd-20170703t164847062z
`category`	mathematics
`json_metadata`	"{"app": "cosgrove/0.0.1rc3", "tags": ["mathematics"]}"
`created`	2017-07-03 16:48:45
`last_update`	2017-07-03 16:48:45
`depth`	1
`children`	0
`net_rshares`	7,788,144,397
`last_payout`	2017-07-10 16:48:45
`cashout_time`	1969-12-31 23:59:59
`total_payout_value`	0.044 SBD
`curator_payout_value`	0.008 SBD
`pending_payout_value`	0.000 SBD
`promoted`	0.000 SBD
`body_length`	709
`author_reputation`	104,981,098,086,561
`root_title`	"Brainsteem Compute #3 Prize Computational Maths Puzzle [Win 40% and 10% in SBD]"
`beneficiaries`	`[]`
`max_accepted_payout`	1,000,000.000 SBD
`percent_steem_dollars`	10,000
`author_curate_reward`	""

properties (23)vote details (1)

voter	weight	wgt%	rshares	pct	time
rycharde	0 B		7,788,144,397	100%

@happychau123 · Jul 3 '17

this is some crazy demand of computational power.....

properties (22)

`post_id`	6,029,564
`author`	happychau123
`permlink`	re-rycharde-brainsteem-compute-3-prize-computational-maths-puzzle-win-40-and-10-in-sbd-20170703t174833460z
`category`	mathematics
`json_metadata`	"{"app": "steemit/0.1", "tags": ["mathematics"]}"
`created`	2017-07-03 17:50:54
`last_update`	2017-07-03 17:50:54
`depth`	1
`children`	2
`net_rshares`	0
`last_payout`	2017-07-10 17:50:54
`cashout_time`	1969-12-31 23:59:59
`total_payout_value`	0.000 SBD
`curator_payout_value`	0.000 SBD
`pending_payout_value`	0.000 SBD
`promoted`	0.000 SBD
`body_length`	53
`author_reputation`	1,501,988,704,632
`root_title`	"Brainsteem Compute #3 Prize Computational Maths Puzzle [Win 40% and 10% in SBD]"
`beneficiaries`	`[]`
`max_accepted_payout`	1,000,000.000 SBD
`percent_steem_dollars`	10,000

@rycharde · Jul 3 '17

$0.30

But can you do it? :-)

I think it's an obvious follow-up question. It's not as hard as finding the highest prime. Each step is simple. 
We can even draw nice graphs like the Collatz conjecture.

👍 cryptoctopus, rycharde, jesta, redpill

properties (23)vote details (4)

voter	rshares	pct
cryptoctopus	33,949,990,617	0.1%
jesta	8,246,384,591	0.1%
redpill	242,883,066	1%
rycharde	8,661,142,673	100%

@happychau123 · Jul 3 '17

$0.09

I don't think I can do this....
Last time to find the highest left truncatable prime is near my hardware's memory limit, This number is for sure larger than that one
but I will try from tmr :)

👍 jesta, happychau123, redpill

properties (23)vote details (3)

voter	rshares	pct
jesta	8,246,773,476	0.1%
redpill	242,883,066	1%
happychau123	7,099,051,955	100%

@rycharde · Jul 3 '17

$0.25

Each prime p(n) has 14 potential values for p(n+1), compared to 9 for the left-truncated primes.

👍 cryptoctopus, jesta, redpill

properties (23)vote details (3)

voter	rshares	pct
cryptoctopus	33,949,990,617	0.1%
jesta	8,246,540,145	0.1%
redpill	242,883,066	1%

@happychau123 · Jul 3 '17

$0.04

For sure I cant do this with 100% confidence level prime checks.
But it sounds still possible to do with strong prime checks :)

👍 happychau123, redpill

properties (23)vote details (2)

voter	weight	wgt%	rshares	pct	time
redpill	0 B		242,883,066	1%
happychau123	0 B		6,975,231,282	100%

@happychau123 · Jul 5 '17

$0.20

Oh god. Too hard for me, any solution from your side? @rycharde

👍 cryptoctopus, jesta, digitalplayer

properties (23)vote details (3)

voter	rshares	pct
cryptoctopus	33,980,060,411	0.1%
digitalplayer	485,791,603	100%
jesta	8,337,226,116	0.1%

@rycharde · Jul 5 '17

All I can say is that I am not the first one to have thought of the question and that there is solution and that it has less than 50 digits.

properties (22)

@happychau123 · Jul 5 '17

OK... lemme try again lol

properties (22)

@quantumdeveloper · Aug 28 '19

$0.02

That was fun!

The result should be:
`8939662423123592347173339993799`
Due to using some java-intern prime check my confidence is *only*
`1-0.5²¹⁴⁷⁴⁸³⁶⁴⁷`(I hate how the unicode superscript characters appear on different heights.)
And here is my (java) code:
```
	static BigInteger TEN = new BigInteger("10");
	static BigInteger MAX = new BigInteger("3");
	static BigInteger [] digits = new BigInteger[10];
	public static void main(String[] args) {
		for(int i = 0; i < 10; i++) {
			digits[i] = new BigInteger(i+"");
		}
		for(int i = 3; i < 10; i += 2) {
			makeChain(new BigInteger(i+""), 1);
		}
	}
	public static void makeChain(BigInteger start, int depth) {
		if(start.isProbablePrime(Integer.MAX_VALUE)) {
			if(start.compareTo(MAX) == 1) {
				MAX = start;
				System.out.println(MAX);
			}
		}
		else
			return;
		for(int i = 1; i < 10; i += 2) {
			if(i == 5)
				continue;
			makeChain(appendRight(start, i), depth+1);
		}
		for(int i = 1; i < 10; i++) {
			makeChain(appendLeft(start, i, depth), depth+1);
		}
	}
	public static BigInteger appendRight(BigInteger bi, int digit) {
		return bi.multiply(TEN).add(digits[digit]);
	}
	public static BigInteger appendLeft(BigInteger bi, int digit, int depth) {
		return bi.add(TEN.pow(depth).multiply(digits[digit]));
	}
```
Well, it's basically just brute-force.

👍 darklands, rycharde

`post_id`	79,522,143
`author`	quantumdeveloper
`permlink`	pwynf0
`category`	mathematics
`json_metadata`	{"tags":["mathematics"],"app":"steemit\/0.1"}
`created`	2019-08-28 18:59:24
`last_update`	2019-08-28 18:59:24
`depth`	1
`children`	5
`net_rshares`	101,137,623,794
`last_payout`	2019-09-04 18:59:24
`cashout_time`	1969-12-31 23:59:59
`total_payout_value`	0.010 SBD
`curator_payout_value`	0.009 SBD
`pending_payout_value`	0.000 SBD
`promoted`	0.000 SBD
`body_length`	1,318
`author_reputation`	4,501,252,062,061
`root_title`	"Brainsteem Compute #3 Prize Computational Maths Puzzle [Win 40% and 10% in SBD]"
`beneficiaries`	`[]`
`max_accepted_payout`	1,000,000.000 SBD
`percent_steem_dollars`	10,000
`author_curate_reward`	""

properties (23)vote details (2)

voter	weight	wgt%	rshares	pct	time
rycharde	0 B		15,070,686,635	26%
darklands	0 B		86,066,937,159	47%

@rycharde · Aug 29 '19

That's great! You *will* find others that were left unanswered.

Some, as in this case, I made up myself but then had a look to see if anybody else had the same idea.

Sometimes the brute force methods need some thoughtful algorithmic assistance to avoid the numbers or processing times going ballistic.

properties (22)

`post_id`	79,543,215
`author`	rycharde
`permlink`	pwzza5
`category`	mathematics
`json_metadata`	{"tags":["mathematics"],"app":"steemit\/0.1"}
`created`	2019-08-29 12:13:18
`last_update`	2019-08-29 12:13:18
`depth`	2
`children`	1
`net_rshares`	0
`last_payout`	2019-09-05 12:13:18
`cashout_time`	1969-12-31 23:59:59
`total_payout_value`	0.000 SBD
`curator_payout_value`	0.000 SBD
`pending_payout_value`	0.000 SBD
`promoted`	0.000 SBD
`body_length`	303
`author_reputation`	19,398,930,083,242
`root_title`	"Brainsteem Compute #3 Prize Computational Maths Puzzle [Win 40% and 10% in SBD]"
`beneficiaries`	`[]`
`max_accepted_payout`	1,000,000.000 SBD
`percent_steem_dollars`	10,000

@quantumdeveloper · Aug 30 '19

You will find others that were left unanswered.

I can't find them. Either I didn't look thoroughly, or there are brainsteems without the tag.

properties (22)

`post_id`	79,590,737
`author`	quantumdeveloper
`permlink`	px2kcb
`category`	mathematics
`json_metadata`	{"tags":["mathematics"],"app":"steemit\/0.1"}
`created`	2019-08-30 21:43:24
`last_update`	2019-08-30 21:43:24
`depth`	3
`children`	0
`net_rshares`	0
`last_payout`	2019-09-06 21:43:24
`cashout_time`	1969-12-31 23:59:59
`total_payout_value`	0.000 SBD
`curator_payout_value`	0.000 SBD
`pending_payout_value`	0.000 SBD
`promoted`	0.000 SBD
`body_length`	142
`author_reputation`	4,501,252,062,061
`root_title`	"Brainsteem Compute #3 Prize Computational Maths Puzzle [Win 40% and 10% in SBD]"
`beneficiaries`	`[]`
`max_accepted_payout`	1,000,000.000 SBD
`percent_steem_dollars`	10,000

@rycharde · Aug 30 '19

You wanted a prize! LOL. Well, as the original prize was a cut of the post profits, then converted to new model steem is probably worth a few cents ;-)

However, worth the effort and interest. Let me offer you either 1 MAPR token or 1 MAXUV token, both worth about 1 STEEM (even after HF21). Let me know which you prefer.

BTW, your solution is correct, and can be found here [on OEIS](https://oeis.org/A137812), one of those amazing internet niche resources.

properties (22)

`post_id`	79,575,304
`author`	rycharde
`permlink`	px1ove
`category`	mathematics
`json_metadata`	{"tags":["mathematics"],"links":["https:\/\/oeis.org\/A137812"],"app":"steemit\/0.1"}
`created`	2019-08-30 10:23:39
`last_update`	2019-08-30 10:23:39
`depth`	2
`children`	2
`net_rshares`	0
`last_payout`	2019-09-06 10:23:39
`cashout_time`	1969-12-31 23:59:59
`total_payout_value`	0.000 SBD
`curator_payout_value`	0.000 SBD
`pending_payout_value`	0.000 SBD
`promoted`	0.000 SBD
`body_length`	459
`author_reputation`	19,398,930,083,242
`root_title`	"Brainsteem Compute #3 Prize Computational Maths Puzzle [Win 40% and 10% in SBD]"
`beneficiaries`	`[]`
`max_accepted_payout`	1,000,000.000 SBD
`percent_steem_dollars`	10,000

@quantumdeveloper · Aug 30 '19

Thank you, for the prize and for the fact that you finally told me wether my solution was right.

I choose to take the MAPR token.

properties (22)

`post_id`	79,583,249
`author`	quantumdeveloper
`permlink`	px2410
`category`	mathematics
`json_metadata`	{"tags":["mathematics"],"app":"steemit\/0.1"}
`created`	2019-08-30 15:51:00
`last_update`	2019-08-30 15:51:00
`depth`	3
`children`	1
`net_rshares`	0
`last_payout`	2019-09-06 15:51:00
`cashout_time`	1969-12-31 23:59:59
`total_payout_value`	0.000 SBD
`curator_payout_value`	0.000 SBD
`pending_payout_value`	0.000 SBD
`promoted`	0.000 SBD
`body_length`	130
`author_reputation`	4,501,252,062,061
`root_title`	"Brainsteem Compute #3 Prize Computational Maths Puzzle [Win 40% and 10% in SBD]"
`beneficiaries`	`[]`
`max_accepted_payout`	1,000,000.000 SBD
`percent_steem_dollars`	10,000

1 reply