Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes
(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]
Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.
Edit: My thanks to nimi for help with golfing the first algorithm via suggesting a pointfree version, and for help with golfing the second algorithm by letting me know that the until keyword exists.
(n#k)q|m<-k-1=1+n*k-until(>n*m)(\z-> -div(-z*k)m)(q*k-mod m q)
A version of the algorithm at the end of my Python answer my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 62 bytes, and has not been golfed down as much as the first, it is faster for large n and small k.
Ungolfed:
First algorithm
jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]
Second algorithm
jos_gkp num step q
-- ceiling throws a type-related fit with ceiling(z*k/(k-1))
-- better to use - div (-z * k) (k - 1)
| m <- step-1 = 1 + num*step - until (>num*m)(\z-> -div (-z*k) m) (q*step - mod m q)
Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes
(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]
Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.
Edit: My thanks to nimi for help with golfing the first algorithm via suggesting a pointfree version, and for help with golfing the second algorithm by letting me know that the until keyword exists.
(n#k)q|m<-k-1=1+n*k-until(>n*m)(\z-> -div(-z*k)m)(q*k-mod m q)
A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 62 bytes, and has not been golfed down as much as the first, it is faster for large n and small k.
Ungolfed:
First algorithm
jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]
Second algorithm
jos_gkp num step q
-- ceiling throws a type-related fit with ceiling(z*k/(k-1))
-- better to use - div (-z * k) (k - 1)
| m <- step-1 = 1 + num*step - until (>num*m)(\z-> -div (-z*k) m) (q*step - mod m q)
Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes
(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]
Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.
Edit: My thanks to nimi for help with golfing the first algorithm via suggesting a pointfree version, and for help with golfing the second algorithm by letting me know that the until keyword exists.
(n#k)q|m<-k-1=1+n*k-until(>n*m)(\z-> -div(-z*k)m)(q*k-mod m q)
A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 62 bytes, and has not been golfed down as much as the first, it is faster for large n and small k.
Ungolfed:
First algorithm
jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]
Second algorithm
jos_gkp num step q
-- ceiling throws a type-related fit with ceiling(z*k/(k-1))
-- better to use - div (-z * k) (k - 1)
| m <- step-1 = 1 + num*step - until (>num*m)(\z-> -div (-z*k) m) (q*step - mod m q)
Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes
(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]
(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]
Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.
Edit: My thanks to nimi for help with golfing the first algorithm via suggesting a pointfree version, and for help with golfing the second algorithm by letting me know that the until keyword exists.
(n?k)q=1+n*k-((q*k-mod(k-1)q)&(n*(k-1)))k
(x&s)m|x<=s=((-div(x*m)(1-m))&s)m|True=x
(n#k)q|m<-k-1=1+n*k-until(>n*m)(\z-> -div(-z*k)m)(q*k-mod m q)
A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 8262 bytes, and has not been golfed down as much as the first, it is faster for large n and small k.
Ungolfed:
First algorithm
jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]
jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]
Second algorithm
jos_gkp num step q = 1 + num*step - by_step (q*step - mod (step-1) q) (num * (step-1)) step
by_step val limit step'
-- ceiling throws a type-related fit with ceiling(x*m/(m-1))
-- better to use - div (-x * m) (m - 1)
| val <= step' = by_step (-div (val * step') (1 - step')) limit step'
| otherwise = val
jos_gkp num step q
-- ceiling throws a type-related fit with ceiling(z*k/(k-1))
-- better to use - div (-z * k) (k - 1)
| m <- step-1 = 1 + num*step - until (>num*m)(\z-> -div (-z*k) m) (q*step - mod m q)
Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes
(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]
Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.
Edit: My thanks to nimi for help with golfing via suggesting a pointfree version.
(n?k)q=1+n*k-((q*k-mod(k-1)q)&(n*(k-1)))k
(x&s)m|x<=s=((-div(x*m)(1-m))&s)m|True=x
A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 82 bytes, and has not been golfed down as much as the first, it is faster for large n and small k
Ungolfed:
First algorithm
jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]
Second algorithm
jos_gkp num step q = 1 + num*step - by_step (q*step - mod (step-1) q) (num * (step-1)) step
by_step val limit step'
-- ceiling throws a type-related fit with ceiling(x*m/(m-1))
-- better to use - div (-x * m) (m - 1)
| val <= step' = by_step (-div (val * step') (1 - step')) limit step'
| otherwise = val
Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes
(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]
Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.
Edit: My thanks to nimi for help with golfing the first algorithm via suggesting a pointfree version, and for help with golfing the second algorithm by letting me know that the until keyword exists.
(n#k)q|m<-k-1=1+n*k-until(>n*m)(\z-> -div(-z*k)m)(q*k-mod m q)
A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 62 bytes, and has not been golfed down as much as the first, it is faster for large n and small k.
Ungolfed:
First algorithm
jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]
Second algorithm
jos_gkp num step q
-- ceiling throws a type-related fit with ceiling(z*k/(k-1))
-- better to use - div (-z * k) (k - 1)
| m <- step-1 = 1 + num*step - until (>num*m)(\z-> -div (-z*k) m) (q*step - mod m q)
Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes
(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]
Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.
Edit: My thanks to nimi for help with golfing via suggesting a pointfree version.
(n?k)q=1+n*k-((q*k-mod(k-1)q)&(n*(k-1)))k
(x&s)m|x<=s=((-div(x*m)(1-m))&s)m|True=x
A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 82 bytes, and has not been golfed down as much as the first, it is faster for large n and small k
Ungolfed:
First algorithm
jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]
Second algorithm
jos_gkp num step q = 1 + num*step - by_step (q*step - mod (step-1) q) (num * (step-1)) step
by_step val limit step'
-- ceiling throws a type-related fit with ceiling(x*m/(m-1))
-- better to use - div (-x * m) (m - 1)
| val <= step' = by_step (-div (val * step') (1 - step')) limit step'
| otherwise = val
Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes
(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]
Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.
Edit: My thanks to nimi for help with golfing via suggesting a pointfree version.
Haskell, (削除) 48 (削除ここまで) (削除) 47 (削除ここまで) 43 bytes
(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]
Based on a Haskell algorithm on the Rosetta Code page of the Josephus function with two inputs. Golfing suggestions are welcome.
Edit: My thanks to nimi for help with golfing via suggesting a pointfree version.
(n?k)q=1+n*k-((q*k-mod(k-1)q)&(n*(k-1)))k
(x&s)m|x<=s=((-div(x*m)(1-m))&s)m|True=x
A version of the algorithm at the end of my Python answer adapted from Concrete Mathematics by Graham, Knuth and Patashnik. Though this algorithm is longer at 82 bytes, and has not been golfed down as much as the first, it is faster for large n and small k
Ungolfed:
First algorithm
jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]
Second algorithm
jos_gkp num step q = 1 + num*step - by_step (q*step - mod (step-1) q) (num * (step-1)) step
by_step val limit step'
-- ceiling throws a type-related fit with ceiling(x*m/(m-1))
-- better to use - div (-x * m) (m - 1)
| val <= step' = by_step (-div (val * step') (1 - step')) limit step'
| otherwise = val