1) For all ordered pairs of positive integers (x,y), we define f(x,y) as follows:
(a) f(x,1) = x.
(b) f(x,y) = 0 if y > x.
(c) f(x + 1,y) = y[f(x,y) + f(x,y - 1)].
Compute (5,5).
2) For each positive integer p, let b(p) denote the unique positive integer k such that \(|k-\sqrt{p}|<\frac{1}{2}\). For example, b(6)=2 and b(23)=5. Find \(S=\sum_{p=1}^{2007} b(p).\)
1) ( Assuming you meant compute f(5,5) )
f(5, 5) = f(4 + 1, 5) = 5[ f(4, 5) + f(4, 5 - 1) ] = 5[ 0 + f(4, 4) ] = 5[ f(4, 4) ] | |||
f(4, 4) = f(3 + 1, 4) = 4[ f(3, 4) + f(3, 4 - 1) ] = 4[ 0 + f(3, 3) ] = 4[ f(3, 3) ] |
| ||
f(3, 3) = f(2 + 1, 3) = 3[ f(2, 3) + f(2, 3 - 1) ] = 3[ 0 + f(2, 2) ] = 3[ f(2, 2) ] | |||
f(2, 2) = f(1 + 1, 2) = 2[ f(1, 2) + f(1, 2 - 1) ] = 2[ 0 + f(1, 1) ] = 2[ f(1, 1) ] |
| ||
f(1, 1) = 1 |
f(2, 2) = 2[ f(1, 1) ] = 2[ | 1 | ] = 2 |
|
f(3, 3) = 3[ f(2, 2) ] = 3[ | 2 | ] = 6 | |
f(4, 4) = 4[ f(3, 3) ] = 4[ | 6 | ] = 24 |
|
f(5, 5) = 5[ f(4, 4) ] = 5[ | -24- | ] = 120 |
2) This one is tricky but here's my attempt...
I started by making this list:
b( | 1 | ) | _ = _ | 1 |
b( | 2 | ) | = | 1 |
b( | 3 | ) | = | 2 |
b( | 4 | ) | = | 2 |
b( | 5 | ) | = | 2 |
b( | 6 | ) | = | 2 |
b( | 7 | ) | = | 3 |
b( | 8 | ) | = | 3 |
b( | 9 | ) | = | 3 |
b( | 10 | ) | = | 3 |
b( | 11 | ) | = | 3 |
b( | 12 | ) | = | 3 |
b( | 13 | ) | = | 4 |
b( | 14 | ) | = | 4 |
b( | 15 | ) | = | 4 |
b( | -16- | ) | = | 4 |
. . . | ||||
b( | 1980 | ) | = | 44 |
b( | 1981 | ) | = | 45 |
b( | 1982 | ) | = | 45 |
b( | 1983 | ) | = | 45 |
b( | 1984 | ) | = | 45 |
b( | 1985 | ) | = | 45 |
b( | 1986 | ) | = | 45 |
b( | 1987 | ) | = | 45 |
b( | 1988 | ) | = | 45 |
b( | 1989 | ) | = | 45 |
b( | 1990 | ) | = | 45 |
b( | 1991 | ) | = | 45 |
b( | 1992 | ) | = | 45 |
b( | 1993 | ) | = | 45 |
b( | 1994 | ) | = | 45 |
b( | 1995 | ) | = | 45 |
b( | 1996 | ) | = | 45 |
b( | 1997 | ) | = | 45 |
b( | 1998 | ) | = | 45 |
b( | 1999 | ) | = | 45 |
b( | 2000 | ) | = | 45 |
b( | 2001 | ) | = | 45 |
b( | 2002 | ) | = | 45 |
b( | 2003 | ) | = | 45 |
b( | 2004 | ) | = | 45 |
b( | 2005 | ) | = | 45 |
b( | 2006 | ) | = | 45 |
b( | 2007 | ) | = | 45 |
By now we can notice something...
b( | 7 | ) = 3 because | 7 | is closer to 9 than 4, and |
b( | 12 | ) = 3 because | 12 | is closer to 9 than 16 |
Between 4 and 9 , there are 4 numbers and 4/2 = 2
Between 9 and 16 there are 6 numbers and 6/2 = 3
So the number of 3's = 1 + 2 + 3 = 6
We can backtrack the previous steps to get...
the number of 3's = \(1+\frac{4}{2}+\frac62\ =\ 1+\frac{9-4-1}{2}+\frac{16-9-1}{2}\ =\ 1+\frac{3^2-(3-1)^2-1}{2}+\frac{(3+1)^2-3^2-1}{2}\)
So in general,
the number of n's = \(1+\frac{n^2-(n-1)^2-1}{2}+\frac{(n+1)^2-n^2-1}{2}\) which simplifies to...
the number of n's = 2n
This agrees with the list from earlier!!!
Except the number of 45's is only 27 because the list ends at b(2007)
\(\sum\limits_{p=1}^{2007}b(p)\ =\ b(1)+b(2)+b(3)+b(4)+b(5)+b(6)+b(7)+\dots+b(2006)+b(2007)\\~\\ \sum\limits_{p=1}^{2007}b(p)\ =\ 1+1+2+2+2+2+3+\dots+45+45\\~\\ \sum\limits_{p=1}^{2007}b(p)\ =\ 2(1)+4(2)+6(3)+\dots+88(44)+27(45)\\~\\ \sum\limits_{p=1}^{2007}b(p)\ =\ \sum\limits_{k=1}^{44}(2k)(k)\quad+\ 27(45)\\~\\ \sum\limits_{p=1}^{2007}b(p)\ =\ \sum\limits_{k=1}^{44}(2k)(k)\quad+\ 27(45)\\~\\ \sum\limits_{p=1}^{2007}b(p)\ =\ 2\sum\limits_{k=1}^{44}k^2\quad+\ 27(45)\\~\\ \sum\limits_{p=1}^{2007}b(p)\ =\ 2(\frac{44(44+1)(2(44)+1)}{6})\quad+\ 27(45)\\~\\ \sum\limits_{p=1}^{2007}b(p)\ =\ 58740\quad+\ 1215\\~\\ \sum\limits_{p=1}^{2007}b(p)\ =\ 59955 \)
P.S. There definitely might be a better way to do it...
Here is a short computer code to verify what hetictar got by summing them up th hard way!
a=1; b=1; c=2007;p=0;d=(abs(a - sqrt b);f=if(abs d < 1/2, goto6, goto8);printa;p=p+a; b++; if(b<=c,goto4,0);b=1;a++;if(a<=c, goto4,0);printp
Sum total =59,955
Just in case anybody wants to see the entire list of integers, here it is (all 2007 integers)! :
1 1 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 44 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 =>> 2007 terms =Sum total = 59,955