How to speed up program execution? 🤔🧐

Question

How to speed up my code that creates a sequence: 1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 10101 ...?
Need to find the n-th term of the sequence of numbers, the number n - can be healthy - 10 ** 9.

n=int(input())
sequence=[1, 10, 100, 101]
s_element=100
while len(sequence)<=n:
j=0
s_element*=10
sequence.append(s_element)
new_element=str(s_element+sequence[j])
while new_element[1]!='1' and len(sequence)<=n:
j+=1
sequence.append(int(new_element))
new_element=str(s_element+sequence[j])
print(sequence[n-1])

Answer 1

The Fibonacci numbers are 1, 2, 3, 5, 8, 13, 21, 34, ...

The 17th term of your sequence is 100101, and 13*(1) + 8*(0) + 5*(0) + 3*(1) + 2*(0) + 1*(1) = 17 is the Zeckendorf representation of 17.

Similarly, the 42th term of your sequence is 10010000, and 34*(1) + 21*(0) + 13*(0) + 8*(1) + 5*(0) + 3*(0) + 2*(0) + 1*(0) = 42 is the Zeckendorf representation of 42.

So the n-th term of your sequence is the Zeckendorf representation of n.

Answer 2

Maybe tell us how you even get the sequence ?

Answer 3

Do it in C++ maybe.

P.S: or better still, look at Diego's answer.

Answer 4

Alexander yes I just noticed, no need for continuation 😂😂 just include that description you gave me in the answer

Answer 5

Diego great one 👌 exactly what I was looking for. I tried to find a sequence by looking at the numbers, but couldn't find any relation. Thanks!

Answer 6

Take a look at the Zeckendorf representation of a number.

https://oeis.org/A014417

https://oeis.org/wiki/Zeckendorf_representation

Answer 7

Diego Ooh, cool, thank you very much!

Answer 8

Diego Now I quickly find the n-th term of the sequence of numbers.
Here is my code:
https://code.sololearn.com/cst8t5LWEi7I/?ref=app

Answer 9

Continuation of the sequence:
1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 10101, 100000, 100001, 100010, 100100, 100101, 101000, 101001, 101010, 1000000, 1000001, 1000010, 1000100, 1000101, 1001000, 1001001, 1001010, 1010000, 1010001, 1010010, 1010100, 1010101, 10000000, 10000001, 10000010, 10000100, 10000101, 10001000, 10001001, 10001010, 10010000, 10010001, 10010010, 10010100, 10010101, 10100000, 10100001, 10100010, 10100100, 10100101, 10101000, 10101001, 10101010, 100000000, 100000001, 100000010, 100000100, 100000101, 100001000, 100001001, 100001010, 100010000, 100010001, 100010010, 100010100, 100010101, 100100000, 100100001, 100100010, 100100100, 100100101, 100101000, 100101001, 100101010, 101000000 ...

Answer 10

Aymane Boukrouh, I hope you had that in mind 😅😁
https://code.sololearn.com/cWZj2b2dny5U/?ref=app

Answer 11

Diego, Thanks of course, but I understood that I didn't understand anything.🤔😶
I don't understand how the sequence is formed mathematically :(

Answer 12

Sonic Thanks) Thanks to Diego , I did the task. C++ I don't know :(

Answer 13

Sonic After some time studying c++, I wrote this:

https://code.sololearn.com/cF9ZbPlz1AuA/?ref=app

😔but it's also slow😔

Answer 14

I create a new number with the condition that it does not have two units in a row.