Skip to content

Instantly share code, notes, and snippets.

@RickCarlino
Created October 26, 2019 20:04
Show Gist options
  • Save RickCarlino/c5fbbc4644dc3f036946fcca5e5d7cdc to your computer and use it in GitHub Desktop.
Save RickCarlino/c5fbbc4644dc3f036946fcca5e5d7cdc to your computer and use it in GitHub Desktop.
Thinking about Bamboo / Lipmaa backlinks

What is This?

It's a pretty neat thing I found!

Please see the Bamboo project for more info.

Lipmaa Iterative Function

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;
};

The First 1,000 Backlinks

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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment