9 Replies - 1240 Views - Last Post: 14 June 2019 - 02:35 PM Rate Topic: -----

#1 DK3250   User is offline

  • Pythonian
  • member icon

Reputation: 534
  • View blog
  • Posts: 1,678
  • Joined: 27-December 13

Summer Challenge

Post icon  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   User is offline

  • Pythonian
  • member icon

Reputation: 534
  • View blog
  • Posts: 1,678
  • Joined: 27-December 13

Re: Summer Challenge

Posted 09 June 2019 - 12:10 PM

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

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.
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12606
  • View blog
  • Posts: 45,745
  • 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

Was This Post Helpful? 1
  • +
  • -

#4 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11547
  • View blog
  • Posts: 19,641
  • 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
Was This Post Helpful? 1
  • +
  • -

#5 DK3250   User is offline

  • Pythonian
  • member icon

Reputation: 534
  • View blog
  • Posts: 1,678
  • 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

Was This Post Helpful? 0
  • +
  • -

#6 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11547
  • View blog
  • Posts: 19,641
  • 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.
Was This Post Helpful? 1
  • +
  • -

#7 albert003   User is offline

  • D.I.C Addict

Reputation: 29
  • View blog
  • Posts: 709
  • 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


I'm reading your explanation and read this website for more information.
https://www.mathsisf...me_numbers.html

Not sure if I'm doing it right.
Was This Post Helpful? 1
  • +
  • -

#8 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11547
  • View blog
  • Posts: 19,641
  • 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
Was This Post Helpful? 1
  • +
  • -

#9 DK3250   User is offline

  • Pythonian
  • member icon

Reputation: 534
  • View blog
  • Posts: 1,678
  • 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.

An up-vote for your courage :innocent:
Was This Post Helpful? 0
  • +
  • -

#10 DK3250   User is offline

  • Pythonian
  • member icon

Reputation: 534
  • View blog
  • Posts: 1,678
  • 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

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1