# Knödel numbers - Find Kn

## Knödel Numbers

The Knödel numbers are a set of sequences. Specifically, the Knödel numbers for a positive integer n are the set of composite numbers m, such that all i < m, coprime to m, satisfy i^(m-n) = 1 (mod m). The set of Knödel numbers for a specific n is denoted Kn. (Wikipedia).

For example, K1 are the Carmichael numbers, and OEIS A002997. They go like: {561, 1105, 1729, 2465, 2821, 6601, ... }. K2 is OEIS A050990 and goes like, {4, 6, 8, 10, 12, 14, 22, 24, 26, ... }.

Your task is to write a program/function/etc. that takes two numbers, n and p. It should return the first p numbers of the Knödel Sequence, Kn.

This is , so shortest code in bytes wins!

## Examples

1, 6   ->   [561, 1105, 1729, 2465, 2821, 6601]
2, 3   ->   [4, 6, 8]
4, 9   ->   [6, 8, 12, 16, 20, 24, 28, 40, 44]
3, 1   ->   
3, 0   ->   []
21, 21 ->   [45, 57, 63, 85, 105, 117, 147, 231, 273, 357, 399, 441, 483, 585, 609, 651, 741, 777, 861, 903, 987]

• Why is 4 not in the sequence K_4? i^(4-4) = 1 mod 4 is always true. – isaacg Jul 27 '15 at 16:13
• @isaacg MathWorld has the additional condition that m > n. – Martin Ender Jul 27 '15 at 16:49

# Pyth, 29 28 bytes

.f&tPZ!f&q1iTZt%^T-ZQZSZvzhQ


1 byte saved thanks to Jakube and orlp.

Demonstration.

Input in the form

p
n


A fairly straightforward calculation. Relative primeness is checked via Pyth's gcd function. This code showcases .f, Pyth's "first n satisfying" function.

I have incorporated the implicit condition that m > n by starting the search for m values at n + 1.

Very straightforward implementation. Defines a binary operator n!p.

n!p=take p[m|m<-[n+1..],any((<1).mod m)[2..m-1],and[i^(m-n)modm<2|i<-[1..m],gcd i m<2]]


Example:

Prelude> 4!9
[6,8,12,16,20,24,28,40,44]

• What is m>n for? – rubik Jul 27 '15 at 14:21
• I have no idea. I was getting negative exponent errors on 21!21, and adding that in solved the problem. – Lynn Jul 27 '15 at 17:31
• I installed Haskell to try and figure out how to get rid of the m>n&& bit, changing m<-[4..] to m<-[n+1..] seems to work. You also get a byte count of 91! – Kade Jul 27 '15 at 18:21
• Neat! Thanks, @Vioz. – Lynn Jul 27 '15 at 19:08
• @Vioz- So you meddled with Haskell without knowing Haskell before? How did you do it? – proud haskeller Jul 28 '15 at 22:16

a#b=gcd a b>1