|
|
A230387
|
|
Least sum of a set of n odious numbers (A000069) such that the sum of two or more is an evil number (A001969).
|
|
4
|
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Is this sequence finite, or is there for any n at least one admissible set of n odious numbers, i.e., such that any sum of two or more elements add up to an evil number?
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
For n=1 to 4, we have the sets
n=1: {1} with sum = 1,
n=2: {1, 2} with sum = 3
n=3: {2, 7, 8} with sum = 17,
n=4: {4, 19, 49, 67} with sum = 139.
E.g., for n=3, the numbers 2, 7 and 8 have an odd bit sum, but 2+7, 2+8, 7+8 and 2+7+8 all have an odd bit sum.
For n=4, we also have the admissible set {14, 31, 44, 61} which has a smaller maximal element, but a larger total sum.
n=5: {42, 84, 138, 174, 357} with sum = 795.
n=6: {168, 348, 372, 702, 906, 1407} with sum = 3903.
n=7: {2273, 2274, 2276, 2280, 2288, 3296, 13888} with sum = 28575.
|
|
PROG
|
(PARI) A69=select(is_A69=n->bittest(hammingweight(n), 0), vector(700, n, n)); A230387(n, m=9e9)={ local(v=vector(n, i, i), ve=vector(n, i, A69[i]), t=0, s=vector(n, i, if(i>1, A230387(i-1))), ok(e)=!forstep(i=3, 2^#e-1, 2, is_A69( sum( j=1, #t=vecextract(e, i), t[j] )) && return), inc(i)=for(j=1, n-i, v[j]=j); for(j=n-i+1, n-1, v[j]++<v[j+1] && return(ve[j]=A69[v[j]]); ve[j]=A69[v[j]=j])/*end for*/; ve[n]=A69[v[n]++]); /*end of local()*/ while( s[n]+ve[n]<m, for(i=2, n, s[n-i+1]+sum(j=n-i+1, n, ve[j]) < m && ok(vecextract(ve, 2^n-2^(n-i))) && next; inc(i); next(2)); m=min(sum(j=1, n, ve[j]), m); inc(n)); m} /* Note: The code may find a(n) earlier but won't return it unless A69 is precomputed up to the limit a(n) - a(n-1); so e.g. 700 is enough for a(5).*/
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,base,more,hard
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|