|
%I #46 Mar 11 2019 03:26:45
%S 1,2,4,8,17,37,86,199,475,1138,2769,6748,16613,40904,101317,251401,
%T 624958,1555940,3882708,9701790,24276866,60817940,152508653,382828565,
%U 961859364,2418662434,6086480305,15327208770,38622901484,97384378728,245686368946,620158662562
%N Number of multisets {1^k1, 2^k2, ..., n^kn}, ki >= 0, with the sum of reciprocals <= 1.
%C The number of distinct sums of reciprocals is given by A212606.
%H Dexter Senft, <a href="/A212658/b212658.txt">Table of n, a(n) for n = 0..36</a>
%o (C#)
%o /* For n=43 or greater, the least common multiple of the numbers 1..n requires more than 64 bits to represent, and C# has no such native data type. */
%o using System;
%o using System.Collections.Generic;
%o namespace A212658 {
%o class Program {
%o static long Result;
%o static long GCD(long n, long m) {
%o long mod;
%o long j = n<m ? m : n;
%o long k = n<m ? n : m;
%o while (true) if ((mod = k%j) == 0)
%o return j; else { k=j; j=mod; }
%o }
%o static long LCM(int n) { // This produces A003418
%o return n<=1 ? 1 : LCM(n-1) / GCD(LCM(n-1), n) * n;
%o }
%o static void Main(string[] args) {
%o List<long> numbers = new List<long>();
%o for (int n=1; n<=42; n++) {
%o long lcm= LCM(n);
%o numbers.Clear();
%o Result = 0;
%o for (int i=2; i<=n; i++) numbers.Add(lcm/i);
%o Count(lcm, numbers, 0);
%o Console.Write(n.ToString() + ": " + (Result+2).ToString() + "\n");
%o }
%o }
%o static void Count(long Target, List<long> L, int At) {
%o if (At >= L.Count) return;
%o if (L[At] <= Target) {
%o Result++;
%o long AmtLeft = Target - L[At];
%o if (AmtLeft >= L[L.Count-1]) Count(AmtLeft, L, At);
%o }
%o Count(Target, L, At+1);
%o return;
%o }
%o }
%o }
%o /* _Dexter Senft_, Feb 07 2019 */
%Y Cf. A212657, A212606, A212607, A020473, A092669, A092671, A208480, A003418.
%K nonn
%O 0,2
%A _Max Alekseyev_, May 23 2012
%E a(24)-a(25) from _Alois P. Heinz_, Nov 20 2017
%E a(26)-a(31) from _Dexter Senft_, Feb 07 2019
| 