-
-
Notifications
You must be signed in to change notification settings - Fork 2.5k
/
sequence.go
30 lines (23 loc) · 667 Bytes
/
sequence.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// The Moser-de Bruijn sequence is the sequence obtained by
// adding up the distinct powers of the number 4 (For example 1, 4, 16, 64, etc).
// You can get more details on https://en.wikipedia.org/wiki/Moser%E2%80%93de_Bruijn_sequence.
package moserdebruijnsequence
func MoserDeBruijnSequence(number int) []int {
sequence := []int{}
for i := 0; i < number; i++ {
res := generateNthTerm(i)
sequence = append(sequence, res)
}
return sequence
}
func generateNthTerm(num int) int {
if num == 0 || num == 1 {
return num
}
//number is even
if num%2 == 0 {
return 4 * generateNthTerm(num/2)
}
//number is odd
return 4*generateNthTerm(num/2) + 1
}