Skip to main content
MathOverflow

Return to Question

deleted 268 characters in body
Source Link
Notamathematician
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24
  • Let $W(n, k, m)$ be an integer coefficients defined for $n > 0, 1 \leqslant k \leqslant n, m > 0$$0 \leqslant k \leqslant n, m > 0$ with $W(n,k,m)=0$ for $n \leqslant 0$$n < 0$ or $k \leqslant 0$$k < 0$ such that

$$ W(n, k, m) = (k-m+1)W(n-1, k, m) + (n-k+1)W(n-1, k-1, m) + [m > 1]W(n, k, m-1), \\ W(1, 1, m) = \binom{m+1}{2} $$$$ W(n, k, m) = (k+m)W(n-1, k, m) + (n-k)W(n-1, k-1, m) + [m > 1]W(n, k, m-1), \\ W(0, 0, m) = 1 $$

For the related sequences in OEIS, see A008292A173018, A062253, A062254, A062255. Note that offsets are the same only for A008292.

  • Let $L(n, k, m)$ be an integer coefficients defined for $n > 0, 1 \leqslant k \leqslant n, 1 \leqslant m \leqslant k$$n > 0, 0 \leqslant k \leqslant n, 0 \leqslant m \leqslant k$ such that

$$ L(n, k, m) = (n - k + 1)!W(n-m+1, k-m+1, m) $$$$ L(n, k, m) = (n-k)!W(n-m, k-m, m+1) $$

$$ p(n, k) = \sum\limits_{i=0}^{k} b(t(n) + (2^i - 1)2^{\ell(t(n))+1})L(s(n), k+1, i+1) $$$$ p(n, k) = \sum\limits_{i=0}^{k} b(t(n) + (2^i - 1)2^{\ell(t(n))+1})L(s(n), k, i) $$

for $0 \leqslant k < s(n)$ with

$$ p(n, s(n)) = b(t(n) + (2^{s(n)} - 1)2^{\ell(t(n))+1}). $$$0 \leqslant k \leqslant s(n)$.

T(n, k) = my(A = 2*n+1, B, C, v1, v2); v1 = []; while(A > 0, B=valuation(A, 2); v1=concat(v1, B+1); A \= 2^(B+1)); v1 = Vecrev(v1); A = #v1; v2 = vector(A, i, 1);  for(i=1, A-1, B = A-i; for(j=1, B, C = B-j+k+1; v2[j] = v2[j]*C^v1[B] - v2[j+1]*(C-1)^v1[B])); v2[1]
a(n) = T(n, 1)
s(n) = if(n==0, 0); my(bL = binarylogint(n, 2), rA = #b1 << (L+1) - n - 1); for(i=2,L #b,- if(!b[i]A == 0, return(i-1), logint(A, 2)); r
t(n) = my(L = logint(n, 2), A = L - s(n) + 1); n - 1 << (L+1) + 1 << A
r(n) = my(A = t(n)); logint((n-A)/((1 << s(n)) - 1) >> (if(A == 0, -1, logint(A, 2)) + 1), 2)
W(n, k, m) = if(n < 10 || k < 10, 0, if(n == 10 && k == 1, binomial(m+10, 2)1, (k+m-1)*W(n-1, k, m) + (n-k+1k)*W(n-1, k-1, m) + if(m>1, W(n, k, m-1))))
L(n, k, m) = (n-k+1k)!*W(n-m+1m, k-m+1m, mm+1)
b(n) = my(A = logint(n+1, 2)); if((n+1) == 1 << A, a(2^100*n+123456), sum(i=0, s(n), p(n, s(n)-i)/i!*sum(j=0, i, (s(n)-j+1)^r(n)*binomial(i, j)*(-1)^j)))
p(n, k) = if(k == s(n), b(t(n)+(2^s(n)-1)*2^(if(t(n)==0,-1,logint(t(n), 2))+1)), sum(i=0, k, b(t(n)+(2^i-1)*2^(if(t(n)==0,-1,logint(t(n), 2))+1))*L(s(n), k+1k, i+1)i))
test(n) = b(n) == a(2^100*n+123456)
  • Let $W(n, k, m)$ be an integer coefficients defined for $n > 0, 1 \leqslant k \leqslant n, m > 0$ with $W(n,k,m)=0$ for $n \leqslant 0$ or $k \leqslant 0$ such that

$$ W(n, k, m) = (k-m+1)W(n-1, k, m) + (n-k+1)W(n-1, k-1, m) + [m > 1]W(n, k, m-1), \\ W(1, 1, m) = \binom{m+1}{2} $$

For the related sequences in OEIS, see A008292, A062253, A062254, A062255. Note that offsets are the same only for A008292.

  • Let $L(n, k, m)$ be an integer coefficients defined for $n > 0, 1 \leqslant k \leqslant n, 1 \leqslant m \leqslant k$ such that

$$ L(n, k, m) = (n - k + 1)!W(n-m+1, k-m+1, m) $$

$$ p(n, k) = \sum\limits_{i=0}^{k} b(t(n) + (2^i - 1)2^{\ell(t(n))+1})L(s(n), k+1, i+1) $$

for $0 \leqslant k < s(n)$ with

$$ p(n, s(n)) = b(t(n) + (2^{s(n)} - 1)2^{\ell(t(n))+1}). $$

T(n, k) = my(A = 2*n+1, B, C, v1, v2); v1 = []; while(A > 0, B=valuation(A, 2); v1=concat(v1, B+1); A \= 2^(B+1)); v1 = Vecrev(v1); A = #v1; v2 = vector(A, i, 1);  for(i=1, A-1, B = A-i; for(j=1, B, C = B-j+k+1; v2[j] = v2[j]*C^v1[B] - v2[j+1]*(C-1)^v1[B])); v2[1]
a(n) = T(n, 1)
s(n) = if(n==0, 0); my(b = binary(n), r = #b); for(i=2, #b, if(!b[i], return(i-1))); r
t(n) = my(L = logint(n, 2), A = L - s(n) + 1); n - 1 << (L+1) + 1 << A
r(n) = my(A = t(n)); logint((n-A)/((1 << s(n)) - 1) >> (if(A == 0, -1, logint(A, 2)) + 1), 2)
W(n, k, m) = if(n < 1 || k < 1, 0, if(n == 1 && k == 1, binomial(m+1, 2), (k+m-1)*W(n-1, k, m) + (n-k+1)*W(n-1, k-1, m) + if(m>1, W(n, k, m-1))))
L(n, k, m) = (n-k+1)!*W(n-m+1, k-m+1, m)
b(n) = my(A = logint(n+1, 2)); if((n+1) == 1 << A, a(2^100*n+123456), sum(i=0, s(n), p(n, s(n)-i)/i!*sum(j=0, i, (s(n)-j+1)^r(n)*binomial(i, j)*(-1)^j)))
p(n, k) = if(k == s(n), b(t(n)+(2^s(n)-1)*2^(if(t(n)==0,-1,logint(t(n), 2))+1)), sum(i=0, k, b(t(n)+(2^i-1)*2^(if(t(n)==0,-1,logint(t(n), 2))+1))*L(s(n), k+1, i+1)))
test(n) = b(n) == a(2^100*n+123456)
  • Let $W(n, k, m)$ be an integer coefficients defined for $0 \leqslant k \leqslant n, m > 0$ with $W(n,k,m)=0$ for $n < 0$ or $k < 0$ such that

$$ W(n, k, m) = (k+m)W(n-1, k, m) + (n-k)W(n-1, k-1, m) + [m > 1]W(n, k, m-1), \\ W(0, 0, m) = 1 $$

For the related sequences in OEIS, see A173018, A062253, A062254, A062255.

  • Let $L(n, k, m)$ be an integer coefficients defined for $n > 0, 0 \leqslant k \leqslant n, 0 \leqslant m \leqslant k$ such that

$$ L(n, k, m) = (n-k)!W(n-m, k-m, m+1) $$

$$ p(n, k) = \sum\limits_{i=0}^{k} b(t(n) + (2^i - 1)2^{\ell(t(n))+1})L(s(n), k, i) $$

for $0 \leqslant k \leqslant s(n)$.

T(n, k) = my(A = 2*n+1, B, C, v1, v2); v1 = []; while(A > 0, B=valuation(A, 2); v1=concat(v1, B+1); A \= 2^(B+1)); v1 = Vecrev(v1); A = #v1; v2 = vector(A, i, 1);  for(i=1, A-1, B = A-i; for(j=1, B, C = B-j+k+1; v2[j] = v2[j]*C^v1[B] - v2[j+1]*(C-1)^v1[B])); v2[1]
a(n) = T(n, 1)
s(n) = my(L = logint(n, 2), A = 1 << (L+1) - n - 1); L - if(A == 0, -1, logint(A, 2))
t(n) = my(L = logint(n, 2), A = L - s(n) + 1); n - 1 << (L+1) + 1 << A
r(n) = my(A = t(n)); logint((n-A)/((1 << s(n)) - 1) >> (if(A == 0, -1, logint(A, 2)) + 1), 2)
W(n, k, m) = if(n < 0 || k < 0, 0, if(n == 0 && k == 0, 1, (k+m)*W(n-1, k, m) + (n-k)*W(n-1, k-1, m) + if(m>1, W(n, k, m-1))))
L(n, k, m) = (n-k)!*W(n-m, k-m, m+1)
b(n) = my(A = logint(n+1, 2)); if((n+1) == 1 << A, a(2^100*n+123456), sum(i=0, s(n), p(n, s(n)-i)/i!*sum(j=0, i, (s(n)-j+1)^r(n)*binomial(i, j)*(-1)^j)))
p(n, k) = sum(i=0, k, b(t(n)+(2^i-1)*2^(if(t(n)==0,-1,logint(t(n), 2))+1))*L(s(n), k, i))
test(n) = b(n) == a(2^100*n+123456)
added 151 characters in body
Source Link
Notamathematician
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24

Please see the update given below. Everything you need to know from the old version of the question are the functions $a(n), \ell(n), s(n), t(n), r(n)$.

$$ W(n, k, m) = (k-m+1)W(n-1, k, m) + (n-k+1)W(n-1, k-1, m) + [m > 1]W(n, k, m-1) $$$$ W(n, k, m) = (k-m+1)W(n-1, k, m) + (n-k+1)W(n-1, k-1, m) + [m > 1]W(n, k, m-1), \\ W(1, 1, m) = \binom{m+1}{2} $$

Please see the update given below.

$$ W(n, k, m) = (k-m+1)W(n-1, k, m) + (n-k+1)W(n-1, k-1, m) + [m > 1]W(n, k, m-1) $$

Please see the update given below. Everything you need to know from the old version of the question are the functions $a(n), \ell(n), s(n), t(n), r(n)$.

$$ W(n, k, m) = (k-m+1)W(n-1, k, m) + (n-k+1)W(n-1, k-1, m) + [m > 1]W(n, k, m-1), \\ W(1, 1, m) = \binom{m+1}{2} $$

added 1225 characters in body
Source Link
Notamathematician
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24

For the related sequences in OEIS, see A008292, A062253, A062254, A062255A062255. Note that offsets are the same only for A008292.

$$ \sum\limits_{i=0}^{s(n)} \frac{p(s(n)-i)}{i!}\sum\limits_{j=0}^{i} (s(n)-j+1)^{r(n)}\binom{i}{j}(-1)^j $$$$ \sum\limits_{i=0}^{s(n)} \frac{p(n, s(n)-i)}{i!}\sum\limits_{j=0}^{i} (s(n)-j+1)^{r(n)}\binom{i}{j}(-1)^j $$

$$ p(k) = \sum\limits_{i=0}^{k} b(t(n) + (2^i - 1)2^{\ell(t(n))+1})L(s(n), k+1, i+1) $$$$ p(n, k) = \sum\limits_{i=0}^{k} b(t(n) + (2^i - 1)2^{\ell(t(n))+1})L(s(n), k+1, i+1) $$

$$ p(s(n)) = b(t(n) + (2^{s(n)} - 1)2^{\ell(t(n))+1}). $$$$ p(n, s(n)) = b(t(n) + (2^{s(n)} - 1)2^{\ell(t(n))+1}). $$

Here is the PARI/GP program to check it numerically:

T(n, k) = my(A = 2*n+1, B, C, v1, v2); v1 = []; while(A > 0, B=valuation(A, 2); v1=concat(v1, B+1); A \= 2^(B+1)); v1 = Vecrev(v1); A = #v1; v2 = vector(A, i, 1);  for(i=1, A-1, B = A-i; for(j=1, B, C = B-j+k+1; v2[j] = v2[j]*C^v1[B] - v2[j+1]*(C-1)^v1[B])); v2[1]
a(n) = T(n, 1)
s(n) = if(n==0, 0); my(b = binary(n), r = #b); for(i=2, #b, if(!b[i], return(i-1))); r
t(n) = my(L = logint(n, 2), A = L - s(n) + 1); n - 1 << (L+1) + 1 << A
r(n) = my(A = t(n)); logint((n-A)/((1 << s(n)) - 1) >> (if(A == 0, -1, logint(A, 2)) + 1), 2)
W(n, k, m) = if(n < 1 || k < 1, 0, if(n == 1 && k == 1, binomial(m+1, 2), (k+m-1)*W(n-1, k, m) + (n-k+1)*W(n-1, k-1, m) + if(m>1, W(n, k, m-1))))
L(n, k, m) = (n-k+1)!*W(n-m+1, k-m+1, m)
b(n) = my(A = logint(n+1, 2)); if((n+1) == 1 << A, a(2^100*n+123456), sum(i=0, s(n), p(n, s(n)-i)/i!*sum(j=0, i, (s(n)-j+1)^r(n)*binomial(i, j)*(-1)^j)))
p(n, k) = if(k == s(n), b(t(n)+(2^s(n)-1)*2^(if(t(n)==0,-1,logint(t(n), 2))+1)), sum(i=0, k, b(t(n)+(2^i-1)*2^(if(t(n)==0,-1,logint(t(n), 2))+1))*L(s(n), k+1, i+1)))
test(n) = b(n) == a(2^100*n+123456)

For the related sequences in OEIS, see A008292, A062253, A062254, A062255. Note that offsets are the same only for A008292.

$$ \sum\limits_{i=0}^{s(n)} \frac{p(s(n)-i)}{i!}\sum\limits_{j=0}^{i} (s(n)-j+1)^{r(n)}\binom{i}{j}(-1)^j $$

$$ p(k) = \sum\limits_{i=0}^{k} b(t(n) + (2^i - 1)2^{\ell(t(n))+1})L(s(n), k+1, i+1) $$

$$ p(s(n)) = b(t(n) + (2^{s(n)} - 1)2^{\ell(t(n))+1}). $$

For the related sequences in OEIS, see A008292, A062253, A062254, A062255. Note that offsets are the same only for A008292.

$$ \sum\limits_{i=0}^{s(n)} \frac{p(n, s(n)-i)}{i!}\sum\limits_{j=0}^{i} (s(n)-j+1)^{r(n)}\binom{i}{j}(-1)^j $$

$$ p(n, k) = \sum\limits_{i=0}^{k} b(t(n) + (2^i - 1)2^{\ell(t(n))+1})L(s(n), k+1, i+1) $$

$$ p(n, s(n)) = b(t(n) + (2^{s(n)} - 1)2^{\ell(t(n))+1}). $$

Here is the PARI/GP program to check it numerically:

T(n, k) = my(A = 2*n+1, B, C, v1, v2); v1 = []; while(A > 0, B=valuation(A, 2); v1=concat(v1, B+1); A \= 2^(B+1)); v1 = Vecrev(v1); A = #v1; v2 = vector(A, i, 1);  for(i=1, A-1, B = A-i; for(j=1, B, C = B-j+k+1; v2[j] = v2[j]*C^v1[B] - v2[j+1]*(C-1)^v1[B])); v2[1]
a(n) = T(n, 1)
s(n) = if(n==0, 0); my(b = binary(n), r = #b); for(i=2, #b, if(!b[i], return(i-1))); r
t(n) = my(L = logint(n, 2), A = L - s(n) + 1); n - 1 << (L+1) + 1 << A
r(n) = my(A = t(n)); logint((n-A)/((1 << s(n)) - 1) >> (if(A == 0, -1, logint(A, 2)) + 1), 2)
W(n, k, m) = if(n < 1 || k < 1, 0, if(n == 1 && k == 1, binomial(m+1, 2), (k+m-1)*W(n-1, k, m) + (n-k+1)*W(n-1, k-1, m) + if(m>1, W(n, k, m-1))))
L(n, k, m) = (n-k+1)!*W(n-m+1, k-m+1, m)
b(n) = my(A = logint(n+1, 2)); if((n+1) == 1 << A, a(2^100*n+123456), sum(i=0, s(n), p(n, s(n)-i)/i!*sum(j=0, i, (s(n)-j+1)^r(n)*binomial(i, j)*(-1)^j)))
p(n, k) = if(k == s(n), b(t(n)+(2^s(n)-1)*2^(if(t(n)==0,-1,logint(t(n), 2))+1)), sum(i=0, k, b(t(n)+(2^i-1)*2^(if(t(n)==0,-1,logint(t(n), 2))+1))*L(s(n), k+1, i+1)))
test(n) = b(n) == a(2^100*n+123456)
deleted 20 characters in body; edited body
Source Link
Notamathematician
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24
added 4 characters in body
Source Link
Notamathematician
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24
added 1378 characters in body
Source Link
Notamathematician
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24
added 8 characters in body
Source Link
Notamathematician
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24
added 246 characters in body
Source Link
Notamathematician
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24
Source Link
Notamathematician
Notamathematician
  • 4.9k
  • 2
  • 11
  • 24