[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/kzPfcVH7    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Aug 29:
; hamming numbers

(define (hamming n)
  (let ((aq (make-vector (+ n 1) 0))
        (i2 1) (i3 1) (i5 1) (x2 2) (x3 3) (x5 5))
    (vector-set! aq 1 1)
    (do ((h 2 (+ h 1))) ((< n h) aq)
      (let ((t (min x2 x3 x5)))
        (vector-set! aq h t)
        (when (= x2 t)
          (set! i2 (+ i2 1))
          (set! x2 (* 2 (vector-ref aq i2))))
        (when (= x3 t)
          (set! i3 (+ i3 1))
          (set! x3 (* 3 (vector-ref aq i3))))
        (when (= x5 t)
          (set! i5 (+ i5 1))
          (set! x5 (* 5 (vector-ref aq i5))))))))

(define (nth-hamming n) (vector-ref (hamming n) n))

(define h1000 (hamming 1000))

(do ((i 1 (+ i 1))) ((< 1000 i))
  (display i) (display #\tab)
  (display (vector-ref h1000 i))
  (newline))

(newline)

(display (nth-hamming 1000000)) (newline)


Output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1	1
2	2
3	3
4	4
5	5
6	6
7	8
8	9
9	10
10	12
11	15
12	16
13	18
14	20
15	24
16	25
17	27
18	30
19	32
20	36
21	40
22	45
23	48
24	50
25	54
26	60
27	64
28	72
29	75
30	80
31	81
32	90
33	96
34	100
35	108
36	120
37	125
38	128
39	135
40	144
41	150
42	160
43	162
44	180
45	192
46	200
47	216
48	225
49	240
50	243
51	250
52	256
53	270
54	288
55	300
56	320
57	324
58	360
59	375
60	384
61	400
62	405
63	432
64	450
65	480
66	486
67	500
68	512
69	540
70	576
71	600
72	625
73	640
74	648
75	675
76	720
77	729
78	750
79	768
80	800
81	810
82	864
83	900
84	960
85	972
86	1000
87	1024
88	1080
89	1125
90	1152
91	1200
92	1215
93	1250
94	1280
95	1296
96	1350
97	1440
98	1458
99	1500
100	1536
101	1600
102	1620
103	1728
104	1800
105	1875
106	1920
107	1944
108	2000
109	2025
110	2048
111	2160
112	2187
113	2250
114	2304
115	2400
116	2430
117	2500
118	2560
119	2592
120	2700
121	2880
122	2916
123	3000
124	3072
125	3125
126	3200
127	3240
128	3375
129	3456
130	3600
131	3645
132	3750
133	3840
134	3888
135	4000
136	4050
137	4096
138	4320
139	4374
140	4500
141	4608
142	4800
143	4860
144	5000
145	5120
146	5184
147	5400
148	5625
149	5760
150	5832
151	6000
152	6075
153	6144
154	6250
155	6400
156	6480
157	6561
158	6750
159	6912
160	7200
161	7290
162	7500
163	7680
164	7776
165	8000
166	8100
167	8192
168	8640
169	8748
170	9000
171	9216
172	9375
173	9600
174	9720
175	10000
176	10125
177	10240
178	10368
179	10800
180	10935
181	11250
182	11520
183	11664
184	12000
185	12150
186	12288
187	12500
188	12800
189	12960
190	13122
191	13500
192	13824
193	14400
194	14580
195	15000
196	15360
197	15552
198	15625
199	16000
200	16200
201	16384
202	16875
203	17280
204	17496
205	18000
206	18225
207	18432
208	18750
209	19200
210	19440
211	19683
212	20000
213	20250
214	20480
215	20736
216	21600
217	21870
218	22500
219	23040
220	23328
221	24000
222	24300
223	24576
224	25000
225	25600
226	25920
227	26244
228	27000
229	27648
230	28125
231	28800
232	29160
233	30000
234	30375
235	30720
236	31104
237	31250
238	32000
239	32400
240	32768
241	32805
242	33750
243	34560
244	34992
245	36000
246	36450
247	36864
248	37500
249	38400
250	38880
251	39366
252	40000
253	40500
254	40960
255	41472
256	43200
257	43740
258	45000
259	46080
260	46656
261	46875
262	48000
263	48600
264	49152
265	50000
266	50625
267	51200
268	51840
269	52488
270	54000
271	54675
272	55296
273	56250
274	57600
275	58320
276	59049
277	60000
278	60750
279	61440
280	62208
281	62500
282	64000
283	64800
284	65536
285	65610
286	67500
287	69120
288	69984
289	72000
290	72900
291	73728
292	75000
293	76800
294	77760
295	78125
296	78732
297	80000
298	81000
299	81920
300	82944
301	84375
302	86400
303	87480
304	90000
305	91125
306	92160
307	93312
308	93750
309	96000
310	97200
311	98304
312	98415
313	100000
314	101250
315	102400
316	103680
317	104976
318	108000
319	109350
320	110592
321	112500
322	115200
323	116640
324	118098
325	120000
326	121500
327	122880
328	124416
329	125000
330	128000
331	129600
332	131072
333	131220
334	135000
335	138240
336	139968
337	140625
338	144000
339	145800
340	147456
341	150000
342	151875
343	153600
344	155520
345	156250
346	157464
347	160000
348	162000
349	163840
350	164025
351	165888
352	168750
353	172800
354	174960
355	177147
356	180000
357	182250
358	184320
359	186624
360	187500
361	192000
362	194400
363	196608
364	196830
365	200000
366	202500
367	204800
368	207360
369	209952
370	216000
371	218700
372	221184
373	225000
374	230400
375	233280
376	234375
377	236196
378	240000
379	243000
380	245760
381	248832
382	250000
383	253125
384	256000
385	259200
386	262144
387	262440
388	270000
389	273375
390	276480
391	279936
392	281250
393	288000
394	291600
395	294912
396	295245
397	300000
398	303750
399	307200
400	311040
401	312500
402	314928
403	320000
404	324000
405	327680
406	328050
407	331776
408	337500
409	345600
410	349920
411	354294
412	360000
413	364500
414	368640
415	373248
416	375000
417	384000
418	388800
419	390625
420	393216
421	393660
422	400000
423	405000
424	409600
425	414720
426	419904
427	421875
428	432000
429	437400
430	442368
431	450000
432	455625
433	460800
434	466560
435	468750
436	472392
437	480000
438	486000
439	491520
440	492075
441	497664
442	500000
443	506250
444	512000
445	518400
446	524288
447	524880
448	531441
449	540000
450	546750
451	552960
452	559872
453	562500
454	576000
455	583200
456	589824
457	590490
458	600000
459	607500
460	614400
461	622080
462	625000
463	629856
464	640000
465	648000
466	655360
467	656100
468	663552
469	675000
470	691200
471	699840
472	703125
473	708588
474	720000
475	729000
476	737280
477	746496
478	750000
479	759375
480	768000
481	777600
482	781250
483	786432
484	787320
485	800000
486	810000
487	819200
488	820125
489	829440
490	839808
491	843750
492	864000
493	874800
494	884736
495	885735
496	900000
497	911250
498	921600
499	933120
500	937500
501	944784
502	960000
503	972000
504	983040
505	984150
506	995328
507	1000000
508	1012500
509	1024000
510	1036800
511	1048576
512	1049760
513	1062882
514	1080000
515	1093500
516	1105920
517	1119744
518	1125000
519	1152000
520	1166400
521	1171875
522	1179648
523	1180980
524	1200000
525	1215000
526	1228800
527	1244160
528	1250000
529	1259712
530	1265625
531	1280000
532	1296000
533	1310720
534	1312200
535	1327104
536	1350000
537	1366875
538	1382400
539	1399680
540	1406250
541	1417176
542	1440000
543	1458000
544	1474560
545	1476225
546	1492992
547	1500000
548	1518750
549	1536000
550	1555200
551	1562500
552	1572864
553	1574640
554	1594323
555	1600000
556	1620000
557	1638400
558	1640250
559	1658880
560	1679616
561	1687500
562	1728000
563	1749600
564	1769472
565	1771470
566	1800000
567	1822500
568	1843200
569	1866240
570	1875000
571	1889568
572	1920000
573	1944000
574	1953125
575	1966080
576	1968300
577	1990656
578	2000000
579	2025000
580	2048000
581	2073600
582	2097152
583	2099520
584	2109375
585	2125764
586	2160000
587	2187000
588	2211840
589	2239488
590	2250000
591	2278125
592	2304000
593	2332800
594	2343750
595	2359296
596	2361960
597	2400000
598	2430000
599	2457600
600	2460375
601	2488320
602	2500000
603	2519424
604	2531250
605	2560000
606	2592000
607	2621440
608	2624400
609	2654208
610	2657205
611	2700000
612	2733750
613	2764800
614	2799360
615	2812500
616	2834352
617	2880000
618	2916000
619	2949120
620	2952450
621	2985984
622	3000000
623	3037500
624	3072000
625	3110400
626	3125000
627	3145728
628	3149280
629	3188646
630	3200000
631	3240000
632	3276800
633	3280500
634	3317760
635	3359232
636	3375000
637	3456000
638	3499200
639	3515625
640	3538944
641	3542940
642	3600000
643	3645000
644	3686400
645	3732480
646	3750000
647	3779136
648	3796875
649	3840000
650	3888000
651	3906250
652	3932160
653	3936600
654	3981312
655	4000000
656	4050000
657	4096000
658	4100625
659	4147200
660	4194304
661	4199040
662	4218750
663	4251528
664	4320000
665	4374000
666	4423680
667	4428675
668	4478976
669	4500000
670	4556250
671	4608000
672	4665600
673	4687500
674	4718592
675	4723920
676	4782969
677	4800000
678	4860000
679	4915200
680	4920750
681	4976640
682	5000000
683	5038848
684	5062500
685	5120000
686	5184000
687	5242880
688	5248800
689	5308416
690	5314410
691	5400000
692	5467500
693	5529600
694	5598720
695	5625000
696	5668704
697	5760000
698	5832000
699	5859375
700	5898240
701	5904900
702	5971968
703	6000000
704	6075000
705	6144000
706	6220800
707	6250000
708	6291456
709	6298560
710	6328125
711	6377292
712	6400000
713	6480000
714	6553600
715	6561000
716	6635520
717	6718464
718	6750000
719	6834375
720	6912000
721	6998400
722	7031250
723	7077888
724	7085880
725	7200000
726	7290000
727	7372800
728	7381125
729	7464960
730	7500000
731	7558272
732	7593750
733	7680000
734	7776000
735	7812500
736	7864320
737	7873200
738	7962624
739	7971615
740	8000000
741	8100000
742	8192000
743	8201250
744	8294400
745	8388608
746	8398080
747	8437500
748	8503056
749	8640000
750	8748000
751	8847360
752	8857350
753	8957952
754	9000000
755	9112500
756	9216000
757	9331200
758	9375000
759	9437184
760	9447840
761	9565938
762	9600000
763	9720000
764	9765625
765	9830400
766	9841500
767	9953280
768	10000000
769	10077696
770	10125000
771	10240000
772	10368000
773	10485760
774	10497600
775	10546875
776	10616832
777	10628820
778	10800000
779	10935000
780	11059200
781	11197440
782	11250000
783	11337408
784	11390625
785	11520000
786	11664000
787	11718750
788	11796480
789	11809800
790	11943936
791	12000000
792	12150000
793	12288000
794	12301875
795	12441600
796	12500000
797	12582912
798	12597120
799	12656250
800	12754584
801	12800000
802	12960000
803	13107200
804	13122000
805	13271040
806	13286025
807	13436928
808	13500000
809	13668750
810	13824000
811	13996800
812	14062500
813	14155776
814	14171760
815	14348907
816	14400000
817	14580000
818	14745600
819	14762250
820	14929920
821	15000000
822	15116544
823	15187500
824	15360000
825	15552000
826	15625000
827	15728640
828	15746400
829	15925248
830	15943230
831	16000000
832	16200000
833	16384000
834	16402500
835	16588800
836	16777216
837	16796160
838	16875000
839	17006112
840	17280000
841	17496000
842	17578125
843	17694720
844	17714700
845	17915904
846	18000000
847	18225000
848	18432000
849	18662400
850	18750000
851	18874368
852	18895680
853	18984375
854	19131876
855	19200000
856	19440000
857	19531250
858	19660800
859	19683000
860	19906560
861	20000000
862	20155392
863	20250000
864	20480000
865	20503125
866	20736000
867	20971520
868	20995200
869	21093750
870	21233664
871	21257640
872	21600000
873	21870000
874	22118400
875	22143375
876	22394880
877	22500000
878	22674816
879	22781250
880	23040000
881	23328000
882	23437500
883	23592960
884	23619600
885	23887872
886	23914845
887	24000000
888	24300000
889	24576000
890	24603750
891	24883200
892	25000000
893	25165824
894	25194240
895	25312500
896	25509168
897	25600000
898	25920000
899	26214400
900	26244000
901	26542080
902	26572050
903	26873856
904	27000000
905	27337500
906	27648000
907	27993600
908	28125000
909	28311552
910	28343520
911	28697814
912	28800000
913	29160000
914	29296875
915	29491200
916	29524500
917	29859840
918	30000000
919	30233088
920	30375000
921	30720000
922	31104000
923	31250000
924	31457280
925	31492800
926	31640625
927	31850496
928	31886460
929	32000000
930	32400000
931	32768000
932	32805000
933	33177600
934	33554432
935	33592320
936	33750000
937	34012224
938	34171875
939	34560000
940	34992000
941	35156250
942	35389440
943	35429400
944	35831808
945	36000000
946	36450000
947	36864000
948	36905625
949	37324800
950	37500000
951	37748736
952	37791360
953	37968750
954	38263752
955	38400000
956	38880000
957	39062500
958	39321600
959	39366000
960	39813120
961	39858075
962	40000000
963	40310784
964	40500000
965	40960000
966	41006250
967	41472000
968	41943040
969	41990400
970	42187500
971	42467328
972	42515280
973	43046721
974	43200000
975	43740000
976	44236800
977	44286750
978	44789760
979	45000000
980	45349632
981	45562500
982	46080000
983	46656000
984	46875000
985	47185920
986	47239200
987	47775744
988	47829690
989	48000000
990	48600000
991	48828125
992	49152000
993	49207500
994	49766400
995	50000000
996	50331648
997	50388480
998	50625000
999	51018336
1000	51200000

519312780448388736089589843750000000000000000000000000000000000000000000000000000000


Create a new paste based on this one


Comments: