Fibonacci without consecutive digits
Output the Nth number in the list of Fibonacci numbers that have no consecutive digits.
Input
- A non-negative integer (if you treat the Fibonacci numbers as zero-indexed) or a positive integer (if you treat the Fibonacci numbers as one-indexed).
Output
- The Nth number in the list of Fibonacci numbers whose base 10 (decimal) representation has no adjacent digits that are consecutive.
- The Fibonacci numbers start with 0 and 1, then each subsequent Fibonacci number is the sum of the previous two Fibonacci numbers.
- You may choose to treat the Fibonacci numbers as either zero-indexed or one-indexed. Either way, the Fibonacci numbers begin with zero:
- Zero-indexed: For input 0, the output is 0.
- One-indexed: For input 1, the output is 0.
- Two digits are consecutive if their absolute difference is 1.
- The consecutive digits can be in either ascending or descending order - either will lead to exclusion from the list.
Examples
Single digit Fibonacci numbers
- A single digit number has no adjacent digits, so all single digit Fibonacci numbers are included.
Two digit Fibonacci numbers
- 34 and 89 are excluded because their digits are consecutive.
- 21 is also excluded due to consecutive digits in descending order.
Non-adjacent consecutive digits
- 46368 contains the digits 4 and 3, which are consecutive digits. However, they are not adjacent (being separated by a 6) so 46368 is included.
Test cases
Test cases are in the format input : output.
Zero-indexed test cases
0 : 0
1 : 1
2 : 1
3 : 2
4 : 3
5 : 5
6 : 8
7 : 13
8 : 55
9 : 144
10 : 377
11 : 1597
12 : 2584
13 : 4181
14 : 17711
15 : 46368
16 : 75025
17 : 196418
18 : 514229
19 : 14930352
20 : 39088169
One-indexed test cases
1 : 0
2 : 1
3 : 1
4 : 2
5 : 3
6 : 5
7 : 8
8 : 13
9 : 55
10 : 144
11 : 377
12 : 1597
13 : 2584
14 : 4181
15 : 17711
16 : 46368
17 : 75025
18 : 196418
19 : 514229
20 : 14930352
21 : 39088169
Scoring
This is a code golf challenge. Your score is the number of bytes in your code. Lowest score for each language wins.
Explanations are optional, but I'm more likely to upvote answers that have one.
[Haskell], 110 bytes ``` ha …
3mo ago
Japt, 17 bytes 0-indexed …
4mo ago
[Python 3], 149 bytes …
10mo ago
[Pyth], 25 23 bytes @f- …
10mo ago
4 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
Haskell, 110 bytes
c[]=1>0
c(a:b:_)|abs(a-b)==1=1<0
c(_:b)=c b
f=0:1:zipWith(+)f(tail f)
h=[g|g<-f,c.map fromEnum.show$g]
r=(h!!)
0 comment threads
Pyth, 25 23 bytes
@f-1aM.:jT;2u+Gs>2GyQU2
First, we generate the Fibonacci numbers:
u+Gs>2GyQU2
U2 range(2), the list [0, 1]
u Apply the following function iteratively,
returning the final result.
+G Add to the end of the current list
s>2G The sum of the last two elements of the current list
yQ Repeat for twice the input number of repetitions
Next, we check for consecutive digits.
@f-1aM.:jT;2
f Filter on the following function
jT; Take the base ten representation of the number.
; accesses T's value in the external scope.
.: 2 Take all pairs of digits.
aM Map pairs to their absolute difference.
-1 Check if 1 is not among the differences.
@ Index the filter result at the input position.
0 comment threads
Python 3, 149 bytes
g=lambda r:r>1and g(r-1)+g(r-2)or r
lambda n:[i for(i)in map(g,range(2*n+2))if(lambda*l:all(abs(n-i)!=1for(n,i)in zip(l,l[1:])))(*map(int,str(i)))][n]
Based on @isaacg's idea of mapping to twice the input, I had a similar thought, but I wasn't sure about the growth rate of the non-adjacent sequence...
Here's a mashed up version of my previous attempt:
j=n
while len(l:=[*filter(lambda*l:all(abs(n-i)!=1for(n,i)in zip(l,l[1:])),[*map(lambda i:[*map(int,str(i))],map(g,range(j:=j+1)))])])<n+1:0
print(l[:-1])
0 comment threads
0 comment threads