32
1
One of my favorite definitions of the prime numbers goes as follows:
2 is the smallest prime.
Numbers larger than 2 are prime if they are not divisible by a smaller prime.
However this definition seems arbitrary, why 2? Why not some other number? Well lets try some other numbers will define n-prime such that
n is the smallest n-prime.
Numbers larger than n are n-prime if they are not divisible by a smaller n-prime.
Task
The task here is to write a program that takes two inputs, a positive integer n and a positive integer a. It will then decide if a is n-prime. Your program should output two distinct values one for "yes, it is n-prime" and one for "no, it is not n-prime".
This is a code-golf question so answers will be scored in bytes with less bytes being better.
Tests
Here are lists of the first 31 primes for n=2 to n=12 (1 is the only 1-prime number)
n=2: [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127]
n=3: [3,4,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127]
n=4: [4,5,6,7,9,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113]
n=5: [5,6,7,8,9,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113]
n=6: [6,7,8,9,10,11,13,15,17,19,23,25,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107]
n=7: [7,8,9,10,11,12,13,15,17,19,23,25,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107]
n=8: [8,9,10,11,12,13,14,15,17,19,21,23,25,29,31,35,37,41,43,47,49,53,59,61,67,71,73,79,83,89,97]
n=9: [9,10,11,12,13,14,15,16,17,19,21,23,25,29,31,35,37,41,43,47,49,53,59,61,67,71,73,79,83,89,97]
n=10: [10,11,12,13,14,15,16,17,18,19,21,23,25,27,29,31,35,37,41,43,47,49,53,59,61,67,71,73,79,83,89]
n=11: [11,12,13,14,15,16,17,18,19,20,21,23,25,27,29,31,35,37,41,43,47,49,53,59,61,67,71,73,79,83,89]
n=12: [12,13,14,15,16,17,18,19,20,21,22,23,25,27,29,31,33,35,37,41,43,47,49,53,55,59,61,67,71,73,77]
4
n=6, a=15
is the first interesting test case. – Neil – 2017-11-24T20:47:13.763@Neil Why do you consider that one interesting? – Post Rock Garf Hunter – 2017-11-24T20:50:30.003
6It's the first place where the non-pattern "a is n-prime iff n≤a<2n or (a≥2n and a is prime)" breaks down. – Misha Lavrov – 2017-11-24T21:36:00.273
2"Numbers larger than 2 are prime if they are not divisible by a smaller prime." - This definition allows any number to be prime. Maybe you want to say iff instead of if? – None – 2017-11-25T00:45:30.653
5@ThePirateBay I don't mean the precise mathematical sense of the word if. I am going to leave it. – Post Rock Garf Hunter – 2017-11-25T01:29:26.933
@MishaLavrov It still appears that the n-primes are the same as the ordinary primes except for "a few" exceptions in the beginning. For example, the 10-primes includes the exceptions
10, 12, 14, 15, 16, 18, 21, 25, 27, 35, 49
(and of course the 10-primes miss the ordinary primes2, 3, 5, 7
). But after 50, any ordinary composite will be divisible by an ordinary prime or by one of the exceptional 10-primes. I think we can prove this in general, for n-primes. – Jeppe Stig Nielsen – 2017-11-26T16:23:07.2801@JeppeStigNielsen It's not very hard to prove this. All composite numbers that are n-prime must have only prime factors that are smaller than n. We also know that no subset of their factors can have a product larger than n because our number would be divisible by that. Thus every n-prime is either 2-prime or the product of 2 numbers less than n. There are only a finite number of pairings of numbers less than n, thus there are only a finite number of composite n-prime numbers. Hopefully that makes sense, I had to abbreviate to fit it in a comment. – Post Rock Garf Hunter – 2017-11-26T19:25:25.927
@JeppeStigNielsen A simple modification on that proof can be used to prove that the upper bound on n-prime composites is n^2-1. – Post Rock Garf Hunter – 2017-11-26T19:43:30.540
1Actually
(n-1)^2
is a stronger upper bound. Here is the proof: Any composite number can be represented asa*b
wherea
andb
are integers greater than 1. If the larger one (lets call ita
) is greater than n and is n-composite, ab is n-composite, becausex | a -> x | ab
, but if its n-prime then ab is still n-composite becauseab | a
. Thus for ab to be n-prime a must be smaller than n. Since the larger is smaller than n both must be smaller than n. Since both a and b are smaller than n ab must be at most(n-1)^2
. – Post Rock Garf Hunter – 2017-11-26T19:49:52.537