# Summer Challenge

Page 1 of 1

## 9 Replies - 3547 Views - Last Post: 14 June 2019 - 02:35 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=416395&amp;s=63332fad68518c9f26d4c58195cc98a2&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 DK3250

• Pythonian

Reputation: 559
• Posts: 1,749
• Joined: 27-December 13

# Summer Challenge

Posted 06 June 2019 - 05:49 PM

Lucky Modulus Number

I’ll start this challenge with a small example.
A list of the first three prime numbers is [2, 3, 5].
A ‘Lucky Modulus Number’ is here defined as the smallest number, N, for which

N % p = p – 1 for all p in the prime list.

In this case N = 29 because
```29 % 2 = 1 = 2 – 1
29 % 3 = 2 = 3 – 1
29 % 5 = 4 = 5 – 1
_____^_______^____     p in prime list
```

Now, as the prime list grows longer, the value of N quickly increases. It is impractical for humans to handle numbers with really many digits, so we report the digit sum i.e. the sum of the individual digits in the result.
The digit sum of 29 is 2 + 9 = 11

The task in this challenge is to find the digit sum of the Lucky Modulus Number of all primes < P
Please report the result for P = 30 and P = 1000

It is ok to report the result quickly. However, in order not to spoil the fun for others, please hold back your code or structural considerations until June 13, 2019.
This is meant to be a totally friendly competition – possibly with some learning….

Is This A Good Question/Topic? 3

## Replies To: Summer Challenge

### #2 DK3250

• Pythonian

Reputation: 559
• Posts: 1,749
• Joined: 27-December 13

## Re: Summer Challenge

Posted 09 June 2019 - 12:10 PM

Hm, many views but no answer to the challenge - yet

Let me see if I can tempt some of you to try.

The question in the challenge is to find answers for P=30 and P=1000

Now, for P=20 I get the result 56 - this is the digit sum of a 7 digit number (9699689) that when divided with any prime lower than 20 produces a remainder one less than the prime in question.

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12648
• Posts: 45,822
• Joined: 27-December 08

## Re: Summer Challenge

Posted 09 June 2019 - 04:42 PM

I recognized the mathematical tool when I saw your challenge, but I haven't had a chance to implement a solution yet.

Spoiler

This post has been edited by macosxnerd101: 09 June 2019 - 04:43 PM

### #4 jon.kiparsky

• Beginner

Reputation: 11652
• Posts: 19,806
• Joined: 19-March 11

## Re: Summer Challenge

Posted 09 June 2019 - 06:40 PM

I have been playing with crude solutions for this, trying to see if I can be smart enough to make crude work
So far, I have a wretchedly slow solution for P=30, not going to bother trying it for P>30.

Next step: I'm going to try math.

dons goggles and safety gear

### #5 DK3250

• Pythonian

Reputation: 559
• Posts: 1,749
• Joined: 27-December 13

## Re: Summer Challenge

Posted 10 June 2019 - 01:50 AM

@macosxnerd101: I had no idea that such a general theory existed.
Also, I find the explanation under the spoiler protection very difficult to understand.
Later I'll give a simpler explanation solving the challenge but less general.

@jon.kiparsky: Solving this by some kind of brute force loop will not do the trick - you need to analyze the problem and find a more direct way.
The number (before doing the digit sum) solving for P=30 has 10 digits - obtainable by brute force.
The number solving for P=1000 has 416 digits - brute force doesn't work here, but the number can still be calculated in milliseconds.

This post has been edited by DK3250: 10 June 2019 - 02:01 AM

### #6 jon.kiparsky

• Beginner

Reputation: 11652
• Posts: 19,806
• Joined: 19-March 11

## Re: Summer Challenge

Posted 10 June 2019 - 06:53 AM

Yep, I'd worked that out. I generally like to try a crude solution first, just to get the parameters of the problem firmly in my mind. It gets some of the initial glitches out of my thinking, which helps when I go to do it the smart way.

### #7 albert003

Reputation: 37
• Posts: 767
• Joined: 15-December 14

## Re: Summer Challenge

Posted 10 June 2019 - 12:55 PM

I'm trying to solve it. I picked 7,11,13. Its been years since I've taken a math class and used prime numbers, so I'm reading up on it. I think I understand what you want me to do and I'm I'm right, this is what I have so far.

31%7 = 3 = 7 - 3
31%11 = 9 = 11 -
31%13

https://www.mathsisf...me_numbers.html

Not sure if I'm doing it right.

### #8 jon.kiparsky

• Beginner

Reputation: 11652
• Posts: 19,806
• Joined: 19-March 11

## Re: Summer Challenge

Posted 10 June 2019 - 01:06 PM

So just to clarify, we're not picking a set of prime numbers, we're taking the set of prime numbers less than some chosen P. So if P=10, we'd have [2,3,5,7], for p=20 we'd have [2,3,5,7,11,13,17,19], etc

Generating a list of primes less than some given value is an old problem, and worth your attention if you haven't played with that before. Some notes on that subject, hopefully useful, here

### #9 DK3250

• Pythonian

Reputation: 559
• Posts: 1,749
• Joined: 27-December 13

## Re: Summer Challenge

Posted 10 June 2019 - 01:09 PM

@albert003:
I think you might have misunderstood the task.
You need to consider all primes up to the limit (30 and 1000).
For the P=30 situation the primes are: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

However, picking just 2 or 3 primes is an excellent way of getting to understand the problem.
I would start with some of the lowest primes to get some easy numbers to play with.

### #10 DK3250

• Pythonian

Reputation: 559
• Posts: 1,749
• Joined: 27-December 13

## Re: Summer Challenge

Posted 14 June 2019 - 02:35 PM

Ok, I promised to give a solution to this challenge.
If you have not solved it; please give it one more try before opening the spoiler protection.

Spoiler

This post has been edited by DK3250: 16 June 2019 - 11:57 AM
Reason for edit:: Detailed explanation added