Thinking about Bamboo / Lipmaa backlinks

bamboo.md

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