10
\$\begingroup\$

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)} \equiv 1 \mod m\$. The set of Knödel numbers for a specific \$n\$ is denoted \$K_n\$. (Wikipedia).

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

Your task

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, \$K_n\$.

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   ->   [9]
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]
Improve this question
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Why is 4 not in the sequence K_4? i^(4-4) = 1 mod 4 is always true. \$\endgroup\$
    – isaacg
    Jul 27, 2015 at 16:13
  • 1
    \$\begingroup\$ @isaacg MathWorld has the additional condition that m > n. \$\endgroup\$
    – Martin Ender
    Jul 27, 2015 at 16:49

3 Answers 3

Reset to default
7
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Haskell, 89 bytes

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)`mod`m<2|i<-[1..m],gcd i m<2]]

Example:

Prelude> 4!9
[6,8,12,16,20,24,28,40,44]
Improve this answer
\$\endgroup\$
9
  • 2
    \$\begingroup\$ What is m>n for? \$\endgroup\$
    – rubik
    Jul 27, 2015 at 14:21
  • 1
    \$\begingroup\$ 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! \$\endgroup\$
    – Kade
    Jul 27, 2015 at 18:21
  • 1
    \$\begingroup\$ Neat! Thanks, @Vioz. \$\endgroup\$
    – Lynn
    Jul 27, 2015 at 19:08
  • 1
    \$\begingroup\$ @Vioz- So you meddled with Haskell without knowing Haskell before? How did you do it? \$\endgroup\$
    – proud haskeller
    Jul 28, 2015 at 22:16
  • 1
    \$\begingroup\$ @Vioz- first time hearing someone saying Haskell is a simple language to understand. I mostly just hear of people who think they don't understand monads or purity or how to do stuff without loops. If Haskell is easy for you, then good luck with learning more of it! (If you want to, of course) \$\endgroup\$
    – proud haskeller
    Jul 29, 2015 at 1:06
2
\$\begingroup\$

Haskell, 90

a#b=gcd a b>1
n!p=take p[m|m<-[n+1..],any(m#)[2..m-1],all(\i->m#i||mod(i^(m-n))m<2)[1..m]]

much the same as @Marius 's answer, though developed independently.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.