It's a pretty neat thing I found!
Please see the Bamboo project for more info.
def lipmaa_iterative(n)
m, po3, x = 1, 3, n
# find k such that (3^k - 1)/2 >= n
while (m < n)
po3 *= 3
m = (po3 - 1) / 2
end
po3 /= 3
# find longest possible backjump
if (m != n)
while x != 0
m = (po3 - 1) / 2
po3 /= 3
x %= m
end
if (m != po3)
po3 = m
end
end
return n - po3
end
function lipmaa_iterative(n: number): number {
let m = 1;
let po3 = 3;
let x = n;
// find k such that(3 ^ k - 1) / 2 >= n
while (m < n) {
po3 *= 3;
m = (po3 - 1) / 2;
}
po3 /= 3;
// find longest possible backjump
if (m != n) {
while (x != 0) {
m = (po3 - 1) / 2;
po3 /= 3;
x %= m;
}
if (m != po3) {
po3 = m;
}
}
return n - po3;
}
int lipmaa_iterative(int n)
{
int m = 1;
int po3 = 3;
int x = n;
// find k such that(3 ^ k - 1) / 2 >= n
while (m < n)
{
po3 *= 3;
m = (po3 - 1) / 2;
}
po3 /= 3;
// find longest possible backjump
if (m != n)
{
while (x != 0)
{
m = (po3 - 1) / 2;
po3 /= 3;
x %= m;
}
if (m != po3)
{
po3 = m;
}
}
return n - po3;
};
An asterisk (*) indicates a "long hop" backlink.
Sequence number... | ...backlinks to sequence number... |
---|---|
1 | 0 |
2 | 1 |
3 | 2 |
4 | * 1 |
5 | 4 |
6 | 5 |
7 | 6 |
8 | * 4 |
9 | 8 |
10 | 9 |
11 | 10 |
12 | * 8 |
13 | * 4 |
14 | 13 |
15 | 14 |
16 | 15 |
17 | * 13 |
18 | 17 |
19 | 18 |
20 | 19 |
21 | * 17 |
22 | 21 |
23 | 22 |
24 | 23 |
25 | * 21 |
26 | * 13 |
27 | 26 |
28 | 27 |
29 | 28 |
30 | * 26 |
31 | 30 |
32 | 31 |
33 | 32 |
34 | * 30 |
35 | 34 |
36 | 35 |
37 | 36 |
38 | * 34 |
39 | * 26 |
40 | * 13 |
41 | 40 |
42 | 41 |
43 | 42 |
44 | * 40 |
45 | 44 |
46 | 45 |
47 | 46 |
48 | * 44 |
49 | 48 |
50 | 49 |
51 | 50 |
52 | * 48 |
53 | * 40 |
54 | 53 |
55 | 54 |
56 | 55 |
57 | * 53 |
58 | 57 |
59 | 58 |
60 | 59 |
61 | * 57 |
62 | 61 |
63 | 62 |
64 | 63 |
65 | * 61 |
66 | * 53 |
67 | 66 |
68 | 67 |
69 | 68 |
70 | * 66 |
71 | 70 |
72 | 71 |
73 | 72 |
74 | * 70 |
75 | 74 |
76 | 75 |
77 | 76 |
78 | * 74 |
79 | * 66 |
80 | * 40 |
81 | 80 |
82 | 81 |
83 | 82 |
84 | * 80 |
85 | 84 |
86 | 85 |
87 | 86 |
88 | * 84 |
89 | 88 |
90 | 89 |
91 | 90 |
92 | * 88 |
93 | * 80 |
94 | 93 |
95 | 94 |
96 | 95 |
97 | * 93 |
98 | 97 |
99 | 98 |
100 | 99 |
101 | * 97 |
102 | 101 |
103 | 102 |
104 | 103 |
105 | * 101 |
106 | * 93 |
107 | 106 |
108 | 107 |
109 | 108 |
110 | * 106 |
111 | 110 |
112 | 111 |
113 | 112 |
114 | * 110 |
115 | 114 |
116 | 115 |
117 | 116 |
118 | * 114 |
119 | * 106 |
120 | * 80 |
121 | * 40 |
122 | 121 |
123 | 122 |
124 | 123 |
125 | * 121 |
126 | 125 |
127 | 126 |
128 | 127 |
129 | * 125 |
130 | 129 |
131 | 130 |
132 | 131 |
133 | * 129 |
134 | * 121 |
135 | 134 |
136 | 135 |
137 | 136 |
138 | * 134 |
139 | 138 |
140 | 139 |
141 | 140 |
142 | * 138 |
143 | 142 |
144 | 143 |
145 | 144 |
146 | * 142 |
147 | * 134 |
148 | 147 |
149 | 148 |
150 | 149 |
151 | * 147 |
152 | 151 |
153 | 152 |
154 | 153 |
155 | * 151 |
156 | 155 |
157 | 156 |
158 | 157 |
159 | * 155 |
160 | * 147 |
161 | * 121 |
162 | 161 |
163 | 162 |
164 | 163 |
165 | * 161 |
166 | 165 |
167 | 166 |
168 | 167 |
169 | * 165 |
170 | 169 |
171 | 170 |
172 | 171 |
173 | * 169 |
174 | * 161 |
175 | 174 |
176 | 175 |
177 | 176 |
178 | * 174 |
179 | 178 |
180 | 179 |
181 | 180 |
182 | * 178 |
183 | 182 |
184 | 183 |
185 | 184 |
186 | * 182 |
187 | * 174 |
188 | 187 |
189 | 188 |
190 | 189 |
191 | * 187 |
192 | 191 |
193 | 192 |
194 | 193 |
195 | * 191 |
196 | 195 |
197 | 196 |
198 | 197 |
199 | * 195 |
200 | * 187 |
201 | * 161 |
202 | 201 |
203 | 202 |
204 | 203 |
205 | * 201 |
206 | 205 |
207 | 206 |
208 | 207 |
209 | * 205 |
210 | 209 |
211 | 210 |
212 | 211 |
213 | * 209 |
214 | * 201 |
215 | 214 |
216 | 215 |
217 | 216 |
218 | * 214 |
219 | 218 |
220 | 219 |
221 | 220 |
222 | * 218 |
223 | 222 |
224 | 223 |
225 | 224 |
226 | * 222 |
227 | * 214 |
228 | 227 |
229 | 228 |
230 | 229 |
231 | * 227 |
232 | 231 |
233 | 232 |
234 | 233 |
235 | * 231 |
236 | 235 |
237 | 236 |
238 | 237 |
239 | * 235 |
240 | * 227 |
241 | * 201 |
242 | * 121 |
243 | 242 |
244 | 243 |
245 | 244 |
246 | * 242 |
247 | 246 |
248 | 247 |
249 | 248 |
250 | * 246 |
251 | 250 |
252 | 251 |
253 | 252 |
254 | * 250 |
255 | * 242 |
256 | 255 |
257 | 256 |
258 | 257 |
259 | * 255 |
260 | 259 |
261 | 260 |
262 | 261 |
263 | * 259 |
264 | 263 |
265 | 264 |
266 | 265 |
267 | * 263 |
268 | * 255 |
269 | 268 |
270 | 269 |
271 | 270 |
272 | * 268 |
273 | 272 |
274 | 273 |
275 | 274 |
276 | * 272 |
277 | 276 |
278 | 277 |
279 | 278 |
280 | * 276 |
281 | * 268 |
282 | * 242 |
283 | 282 |
284 | 283 |
285 | 284 |
286 | * 282 |
287 | 286 |
288 | 287 |
289 | 288 |
290 | * 286 |
291 | 290 |
292 | 291 |
293 | 292 |
294 | * 290 |
295 | * 282 |
296 | 295 |
297 | 296 |
298 | 297 |
299 | * 295 |
300 | 299 |
301 | 300 |
302 | 301 |
303 | * 299 |
304 | 303 |
305 | 304 |
306 | 305 |
307 | * 303 |
308 | * 295 |
309 | 308 |
310 | 309 |
311 | 310 |
312 | * 308 |
313 | 312 |
314 | 313 |
315 | 314 |
316 | * 312 |
317 | 316 |
318 | 317 |
319 | 318 |
320 | * 316 |
321 | * 308 |
322 | * 282 |
323 | 322 |
324 | 323 |
325 | 324 |
326 | * 322 |
327 | 326 |
328 | 327 |
329 | 328 |
330 | * 326 |
331 | 330 |
332 | 331 |
333 | 332 |
334 | * 330 |
335 | * 322 |
336 | 335 |
337 | 336 |
338 | 337 |
339 | * 335 |
340 | 339 |
341 | 340 |
342 | 341 |
343 | * 339 |
344 | 343 |
345 | 344 |
346 | 345 |
347 | * 343 |
348 | * 335 |
349 | 348 |
350 | 349 |
351 | 350 |
352 | * 348 |
353 | 352 |
354 | 353 |
355 | 354 |
356 | * 352 |
357 | 356 |
358 | 357 |
359 | 358 |
360 | * 356 |
361 | * 348 |
362 | * 322 |
363 | * 242 |
364 | * 121 |
365 | 364 |
366 | 365 |
367 | 366 |
368 | * 364 |
369 | 368 |
370 | 369 |
371 | 370 |
372 | * 368 |
373 | 372 |
374 | 373 |
375 | 374 |
376 | * 372 |
377 | * 364 |
378 | 377 |
379 | 378 |
380 | 379 |
381 | * 377 |
382 | 381 |
383 | 382 |
384 | 383 |
385 | * 381 |
386 | 385 |
387 | 386 |
388 | 387 |
389 | * 385 |
390 | * 377 |
391 | 390 |
392 | 391 |
393 | 392 |
394 | * 390 |
395 | 394 |
396 | 395 |
397 | 396 |
398 | * 394 |
399 | 398 |
400 | 399 |
401 | 400 |
402 | * 398 |
403 | * 390 |
404 | * 364 |
405 | 404 |
406 | 405 |
407 | 406 |
408 | * 404 |
409 | 408 |
410 | 409 |
411 | 410 |
412 | * 408 |
413 | 412 |
414 | 413 |
415 | 414 |
416 | * 412 |
417 | * 404 |
418 | 417 |
419 | 418 |
420 | 419 |
421 | * 417 |
422 | 421 |
423 | 422 |
424 | 423 |
425 | * 421 |
426 | 425 |
427 | 426 |
428 | 427 |
429 | * 425 |
430 | * 417 |
431 | 430 |
432 | 431 |
433 | 432 |
434 | * 430 |
435 | 434 |
436 | 435 |
437 | 436 |
438 | * 434 |
439 | 438 |
440 | 439 |
441 | 440 |
442 | * 438 |
443 | * 430 |
444 | * 404 |
445 | 444 |
446 | 445 |
447 | 446 |
448 | * 444 |
449 | 448 |
450 | 449 |
451 | 450 |
452 | * 448 |
453 | 452 |
454 | 453 |
455 | 454 |
456 | * 452 |
457 | * 444 |
458 | 457 |
459 | 458 |
460 | 459 |
461 | * 457 |
462 | 461 |
463 | 462 |
464 | 463 |
465 | * 461 |
466 | 465 |
467 | 466 |
468 | 467 |
469 | * 465 |
470 | * 457 |
471 | 470 |
472 | 471 |
473 | 472 |
474 | * 470 |
475 | 474 |
476 | 475 |
477 | 476 |
478 | * 474 |
479 | 478 |
480 | 479 |
481 | 480 |
482 | * 478 |
483 | * 470 |
484 | * 444 |
485 | * 364 |
486 | 485 |
487 | 486 |
488 | 487 |
489 | * 485 |
490 | 489 |
491 | 490 |
492 | 491 |
493 | * 489 |
494 | 493 |
495 | 494 |
496 | 495 |
497 | * 493 |
498 | * 485 |
499 | 498 |
500 | 499 |
501 | 500 |
502 | * 498 |
503 | 502 |
504 | 503 |
505 | 504 |
506 | * 502 |
507 | 506 |
508 | 507 |
509 | 508 |
510 | * 506 |
511 | * 498 |
512 | 511 |
513 | 512 |
514 | 513 |
515 | * 511 |
516 | 515 |
517 | 516 |
518 | 517 |
519 | * 515 |
520 | 519 |
521 | 520 |
522 | 521 |
523 | * 519 |
524 | * 511 |
525 | * 485 |
526 | 525 |
527 | 526 |
528 | 527 |
529 | * 525 |
530 | 529 |
531 | 530 |
532 | 531 |
533 | * 529 |
534 | 533 |
535 | 534 |
536 | 535 |
537 | * 533 |
538 | * 525 |
539 | 538 |
540 | 539 |
541 | 540 |
542 | * 538 |
543 | 542 |
544 | 543 |
545 | 544 |
546 | * 542 |
547 | 546 |
548 | 547 |
549 | 548 |
550 | * 546 |
551 | * 538 |
552 | 551 |
553 | 552 |
554 | 553 |
555 | * 551 |
556 | 555 |
557 | 556 |
558 | 557 |
559 | * 555 |
560 | 559 |
561 | 560 |
562 | 561 |
563 | * 559 |
564 | * 551 |
565 | * 525 |
566 | 565 |
567 | 566 |
568 | 567 |
569 | * 565 |
570 | 569 |
571 | 570 |
572 | 571 |
573 | * 569 |
574 | 573 |
575 | 574 |
576 | 575 |
577 | * 573 |
578 | * 565 |
579 | 578 |
580 | 579 |
581 | 580 |
582 | * 578 |
583 | 582 |
584 | 583 |
585 | 584 |
586 | * 582 |
587 | 586 |
588 | 587 |
589 | 588 |
590 | * 586 |
591 | * 578 |
592 | 591 |
593 | 592 |
594 | 593 |
595 | * 591 |
596 | 595 |
597 | 596 |
598 | 597 |
599 | * 595 |
600 | 599 |
601 | 600 |
602 | 601 |
603 | * 599 |
604 | * 591 |
605 | * 565 |
606 | * 485 |
607 | 606 |
608 | 607 |
609 | 608 |
610 | * 606 |
611 | 610 |
612 | 611 |
613 | 612 |
614 | * 610 |
615 | 614 |
616 | 615 |
617 | 616 |
618 | * 614 |
619 | * 606 |
620 | 619 |
621 | 620 |
622 | 621 |
623 | * 619 |
624 | 623 |
625 | 624 |
626 | 625 |
627 | * 623 |
628 | 627 |
629 | 628 |
630 | 629 |
631 | * 627 |
632 | * 619 |
633 | 632 |
634 | 633 |
635 | 634 |
636 | * 632 |
637 | 636 |
638 | 637 |
639 | 638 |
640 | * 636 |
641 | 640 |
642 | 641 |
643 | 642 |
644 | * 640 |
645 | * 632 |
646 | * 606 |
647 | 646 |
648 | 647 |
649 | 648 |
650 | * 646 |
651 | 650 |
652 | 651 |
653 | 652 |
654 | * 650 |
655 | 654 |
656 | 655 |
657 | 656 |
658 | * 654 |
659 | * 646 |
660 | 659 |
661 | 660 |
662 | 661 |
663 | * 659 |
664 | 663 |
665 | 664 |
666 | 665 |
667 | * 663 |
668 | 667 |
669 | 668 |
670 | 669 |
671 | * 667 |
672 | * 659 |
673 | 672 |
674 | 673 |
675 | 674 |
676 | * 672 |
677 | 676 |
678 | 677 |
679 | 678 |
680 | * 676 |
681 | 680 |
682 | 681 |
683 | 682 |
684 | * 680 |
685 | * 672 |
686 | * 646 |
687 | 686 |
688 | 687 |
689 | 688 |
690 | * 686 |
691 | 690 |
692 | 691 |
693 | 692 |
694 | * 690 |
695 | 694 |
696 | 695 |
697 | 696 |
698 | * 694 |
699 | * 686 |
700 | 699 |
701 | 700 |
702 | 701 |
703 | * 699 |
704 | 703 |
705 | 704 |
706 | 705 |
707 | * 703 |
708 | 707 |
709 | 708 |
710 | 709 |
711 | * 707 |
712 | * 699 |
713 | 712 |
714 | 713 |
715 | 714 |
716 | * 712 |
717 | 716 |
718 | 717 |
719 | 718 |
720 | * 716 |
721 | 720 |
722 | 721 |
723 | 722 |
724 | * 720 |
725 | * 712 |
726 | * 686 |
727 | * 606 |
728 | * 364 |
729 | 728 |
730 | 729 |
731 | 730 |
732 | * 728 |
733 | 732 |
734 | 733 |
735 | 734 |
736 | * 732 |
737 | 736 |
738 | 737 |
739 | 738 |
740 | * 736 |
741 | * 728 |
742 | 741 |
743 | 742 |
744 | 743 |
745 | * 741 |
746 | 745 |
747 | 746 |
748 | 747 |
749 | * 745 |
750 | 749 |
751 | 750 |
752 | 751 |
753 | * 749 |
754 | * 741 |
755 | 754 |
756 | 755 |
757 | 756 |
758 | * 754 |
759 | 758 |
760 | 759 |
761 | 760 |
762 | * 758 |
763 | 762 |
764 | 763 |
765 | 764 |
766 | * 762 |
767 | * 754 |
768 | * 728 |
769 | 768 |
770 | 769 |
771 | 770 |
772 | * 768 |
773 | 772 |
774 | 773 |
775 | 774 |
776 | * 772 |
777 | 776 |
778 | 777 |
779 | 778 |
780 | * 776 |
781 | * 768 |
782 | 781 |
783 | 782 |
784 | 783 |
785 | * 781 |
786 | 785 |
787 | 786 |
788 | 787 |
789 | * 785 |
790 | 789 |
791 | 790 |
792 | 791 |
793 | * 789 |
794 | * 781 |
795 | 794 |
796 | 795 |
797 | 796 |
798 | * 794 |
799 | 798 |
800 | 799 |
801 | 800 |
802 | * 798 |
803 | 802 |
804 | 803 |
805 | 804 |
806 | * 802 |
807 | * 794 |
808 | * 768 |
809 | 808 |
810 | 809 |
811 | 810 |
812 | * 808 |
813 | 812 |
814 | 813 |
815 | 814 |
816 | * 812 |
817 | 816 |
818 | 817 |
819 | 818 |
820 | * 816 |
821 | * 808 |
822 | 821 |
823 | 822 |
824 | 823 |
825 | * 821 |
826 | 825 |
827 | 826 |
828 | 827 |
829 | * 825 |
830 | 829 |
831 | 830 |
832 | 831 |
833 | * 829 |
834 | * 821 |
835 | 834 |
836 | 835 |
837 | 836 |
838 | * 834 |
839 | 838 |
840 | 839 |
841 | 840 |
842 | * 838 |
843 | 842 |
844 | 843 |
845 | 844 |
846 | * 842 |
847 | * 834 |
848 | * 808 |
849 | * 728 |
850 | 849 |
851 | 850 |
852 | 851 |
853 | * 849 |
854 | 853 |
855 | 854 |
856 | 855 |
857 | * 853 |
858 | 857 |
859 | 858 |
860 | 859 |
861 | * 857 |
862 | * 849 |
863 | 862 |
864 | 863 |
865 | 864 |
866 | * 862 |
867 | 866 |
868 | 867 |
869 | 868 |
870 | * 866 |
871 | 870 |
872 | 871 |
873 | 872 |
874 | * 870 |
875 | * 862 |
876 | 875 |
877 | 876 |
878 | 877 |
879 | * 875 |
880 | 879 |
881 | 880 |
882 | 881 |
883 | * 879 |
884 | 883 |
885 | 884 |
886 | 885 |
887 | * 883 |
888 | * 875 |
889 | * 849 |
890 | 889 |
891 | 890 |
892 | 891 |
893 | * 889 |
894 | 893 |
895 | 894 |
896 | 895 |
897 | * 893 |
898 | 897 |
899 | 898 |
900 | 899 |
901 | * 897 |
902 | * 889 |
903 | 902 |
904 | 903 |
905 | 904 |
906 | * 902 |
907 | 906 |
908 | 907 |
909 | 908 |
910 | * 906 |
911 | 910 |
912 | 911 |
913 | 912 |
914 | * 910 |
915 | * 902 |
916 | 915 |
917 | 916 |
918 | 917 |
919 | * 915 |
920 | 919 |
921 | 920 |
922 | 921 |
923 | * 919 |
924 | 923 |
925 | 924 |
926 | 925 |
927 | * 923 |
928 | * 915 |
929 | * 889 |
930 | 929 |
931 | 930 |
932 | 931 |
933 | * 929 |
934 | 933 |
935 | 934 |
936 | 935 |
937 | * 933 |
938 | 937 |
939 | 938 |
940 | 939 |
941 | * 937 |
942 | * 929 |
943 | 942 |
944 | 943 |
945 | 944 |
946 | * 942 |
947 | 946 |
948 | 947 |
949 | 948 |
950 | * 946 |
951 | 950 |
952 | 951 |
953 | 952 |
954 | * 950 |
955 | * 942 |
956 | 955 |
957 | 956 |
958 | 957 |
959 | * 955 |
960 | 959 |
961 | 960 |
962 | 961 |
963 | * 959 |
964 | 963 |
965 | 964 |
966 | 965 |
967 | * 963 |
968 | * 955 |
969 | * 929 |
970 | * 849 |
971 | 970 |
972 | 971 |
973 | 972 |
974 | * 970 |
975 | 974 |
976 | 975 |
977 | 976 |
978 | * 974 |
979 | 978 |
980 | 979 |
981 | 980 |
982 | * 978 |
983 | * 970 |
984 | 983 |
985 | 984 |
986 | 985 |
987 | * 983 |
988 | 987 |
989 | 988 |
990 | 989 |
991 | * 987 |
992 | 991 |
993 | 992 |
994 | 993 |
995 | * 991 |
996 | * 983 |
997 | 996 |
998 | 997 |
999 | 998 |
1000 | * 996 |