+ 2

How to speed up program execution? 🤔🧐

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])

2nd Jan 2020, 6:23 PM
Oleksandr
Oleksandr - avatar
14 Answers
+ 5
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.
2nd Jan 2020, 8:54 PM
Diego
Diego - avatar
+ 6
Maybe tell us how you even get the sequence ?
2nd Jan 2020, 6:37 PM
Aymane Boukrouh
Aymane Boukrouh - avatar
+ 5
Do it in C++ maybe. P.S: or better still, look at Diego's answer.
4th Jan 2020, 5:46 PM
Sonic
Sonic - avatar
+ 4
Alexander yes I just noticed, no need for continuation 😂😂 just include that description you gave me in the answer
2nd Jan 2020, 6:57 PM
Aymane Boukrouh
Aymane Boukrouh - avatar
+ 4
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!
2nd Jan 2020, 8:57 PM
Aymane Boukrouh
Aymane Boukrouh - avatar
+ 3
Take a look at the Zeckendorf representation of a number. https://oeis.org/A014417 https://oeis.org/wiki/Zeckendorf_representation
2nd Jan 2020, 8:20 PM
Diego
Diego - avatar
+ 2
Diego Ooh, cool, thank you very much!
2nd Jan 2020, 10:05 PM
Oleksandr
Oleksandr - avatar
+ 2
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
2nd Jan 2020, 10:14 PM
Oleksandr
Oleksandr - avatar
+ 1
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 ...
2nd Jan 2020, 6:56 PM
Oleksandr
Oleksandr - avatar
+ 1
2nd Jan 2020, 7:04 PM
Oleksandr
Oleksandr - avatar
+ 1
Diego, Thanks of course, but I understood that I didn't understand anything.🤔😶 I don't understand how the sequence is formed mathematically :(
2nd Jan 2020, 8:39 PM
Oleksandr
Oleksandr - avatar
+ 1
Sonic Thanks) Thanks to Diego , I did the task. C++ I don't know :(
4th Jan 2020, 7:13 PM
Oleksandr
Oleksandr - avatar
+ 1
Sonic After some time studying c++, I wrote this: https://code.sololearn.com/cF9ZbPlz1AuA/?ref=app 😔but it's also slow😔
12th Jan 2020, 12:39 PM
Oleksandr
Oleksandr - avatar
0
I create a new number with the condition that it does not have two units in a row.
2nd Jan 2020, 6:52 PM
Oleksandr
Oleksandr - avatar