10
\$\begingroup\$

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

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

\$\endgroup\$
4
\$\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]
\$\endgroup\$
  • 2
    \$\begingroup\$ What is m>n for? \$\endgroup\$ – rubik Jul 27 '15 at 14:21
  • \$\begingroup\$ I have no idea. I was getting negative exponent errors on 21!21, and adding that in solved the problem. \$\endgroup\$ – Lynn Jul 27 '15 at 17:31
  • 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 '15 at 18:21
  • 1
    \$\begingroup\$ Neat! Thanks, @Vioz. \$\endgroup\$ – Lynn Jul 27 '15 at 19:08
  • \$\begingroup\$ @Vioz- So you meddled with Haskell without knowing Haskell before? How did you do it? \$\endgroup\$ – proud haskeller Jul 28 '15 at 22:16
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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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