tenta-TATA54-20240822-skiss.org

#+title: TATA54 tenta 20240601, lösningskiss
#+author: Jan Snellman

* Preliminärt
5 uppgifter, 3p för varje. Försöker täcka
- Kongruensräkning
- Hensellyft
- Kvadratisk reciprocite
- Kedjebråk
- Pell eller Pytagoranska tripplar


* Gemensamm kod
#+begin_src sage :session :export none
def H_L_tree(f, p: int, r: int):
    vert = [(0,0)]
    for j in range(1,r+1):
        fj = f.change_ring(Integers(p^j))
        fzj = fj.roots(multiplicities=False)
        vert += [(z,j) for z in fzj]
    return DiGraph([vert, 
                    lambda u,v: (u[1] == 1 and v[1] == 0) 
                    or 
                    ( (u[1] == v[1]+1) and ((u[0] - v[0]) % p^v[1] ==0) ) 
                   ])
#+end_src

#+RESULTS:

#+begin_src latex
  \newcommand{\QQ}{\mathbf{Q}}
  \newcommand{\ZZ}{\mathbf{Z}}
#+end_src
* Uppgifterna
** U1
#+begin_src latex
    Hur många lösningar har kongruensen
  \begin{displaymath}
    x^4 +2x +4 \equiv 0 \mod 625
  \end{displaymath}
#+end_src


#+begin_src sage :session 
  p = 5
  k = 4
  q = p^k
  R.<x> = ZZ[]
  f = x^4 + 2*x + 4
  [(s,f.roots(Integers(p^s),multiplicities=False)) for s in range(k+1)]
  df = f.diff()
  df, df(3)
#+end_src

#+RESULTS:
: [(0, [0]), (1, [3]), (2, []), (3, []), (4, [])]
: (4*x^3 + 2, 110)

#+begin_src sage :session :results file :file "nu1.png"
  H_L_tree(f,p,k).show(layout='tree')
#+end_src

#+RESULTS:
[[file:nu1.png]]


** U2


#+begin_src latex
  Hitta alla rationella punkter på kurvan
  \begin{displaymath}
    x^2 +2y^2 - 1 = 0
  \end{displaymath}

#+end_src

Parametrisera med lutning, rationell punkt (-1,0)

#+begin_src sage :session
var('s,t,x,y')
kurva = x^2 + 2*y^2-1
linje = y - t*(x+1)
soln = solve([kurva,linje],[x,y])
soln
rp = soln[0]
rp
soln2 = solve([linje],[t])
soln2
#+end_src

#+RESULTS:
: (s, t, x, y)
: [[x == -(2*t^2 - 1)/(2*t^2 + 1), y == 2*t/(2*t^2 + 1)], [x == -1, y == 0]]
: [x == -(2*t^2 - 1)/(2*t^2 + 1), y == 2*t/(2*t^2 + 1)]
: [t == y/(x + 1)]

#+begin_src sage :session :results file :file "nu2.png"
epsi = 10^(-1)
parametric_plot((rp[0].rhs(),rp[1].rhs()), (t,+epsi,1/sqrt(7) -epsi) )
#+end_src

#+RESULTS:
[[file:nu2.png]]

** U3


** U4 
#+begin_src latex
   Låt \(\tau(n)\) beteckna antalet positiva delare till heltalet \(n\).
    Visa  att
    \[
      \sum_{k=1}^n \tau(k) = \sum_{k=1}^n  \left \lfloor \frac{n}{k} \right \rfloor
    \]
#+end_src

#+begin_src sage :session
n=20
[(k,number_of_divisors(k),floor(n/k)) for k in range(1,n+1)]

def u(n):
    return sum(number_of_divisors(k) for k in range(1,n+1))

def w(n):
    return sum(floor(n/k) for k in range(1,n+1))

[(k,u(k),w(k)) for k in range(1,20+1)]

#+end_src

#+RESULTS:
#+begin_example
[(1, 1, 20),
 (2, 2, 10),
 (3, 2, 6),
 (4, 3, 5),
 (5, 2, 4),
 (6, 4, 3),
 (7, 2, 2),
 (8, 4, 2),
 (9, 3, 2),
 (10, 4, 2),
 (11, 2, 1),
 (12, 6, 1),
 (13, 2, 1),
 (14, 4, 1),
 (15, 4, 1),
 (16, 5, 1),
 (17, 2, 1),
 (18, 6, 1),
 (19, 2, 1),
 (20, 6, 1)]
[(1, 1, 1),
 (2, 3, 3),
 (3, 5, 5),
 (4, 8, 8),
 (5, 10, 10),
 (6, 14, 14),
 (7, 16, 16),
 (8, 20, 20),
 (9, 23, 23),
 (10, 27, 27),
 (11, 29, 29),
 (12, 35, 35),
 (13, 37, 37),
 (14, 41, 41),
 (15, 45, 45),
 (16, 50, 50),
 (17, 52, 52),
 (18, 58, 58),
 (19, 60, 60),
 (20, 66, 66)]
#+end_example

** U5
#+begin_src latex

#+end_src

#+RESULTS:
#+begin_export latex
Hur många lösningar har ekvationen
\(x^2 \equiv 187 \mod 23\)?
Hur många har
\(x^2 \equiv 23 \mod 187\)?
#+end_export


#+begin_src sage :session
p = 23
a = 11*17
a
legendre_symbol(a,p)

R.<x> = ZZ[]
f = x^2 -23
f.roots(Integers(187),multiplicities=False)
f.roots(Integers(11),multiplicities=False)
f.roots(Integers(17),multiplicities=False)

g = x^2 -187
g.roots(Integers(23),multiplicities=False)
#+end_src

#+RESULTS:
: 187
: 1
: []
: [10, 1]
: []
: [16, 7]

** U7
#+begin_src latex
Låt \(r=117/119\). Hitta positiva heltal \(a,b\) med \(b < 119\)
så att \(|a/b - r| \le |c/d -r|\) för alla
positiva heltal \(c,d\) med \(d < 119\).
#+end_src

#+RESULTS:
#+begin_export latex
Låt \(r=117/119\). Hitta positiva heltal \(a,b\) med \(b < 119\)
så att \(|a/b - r| \le |c/d -r|\) för alla
positiva heltal \(c,d\) med \(d < 119\).
#+end_export

#+begin_src sage :session
p=117
q= 119
r=p/q
cf = continued_fraction(r)
cf
best = cf.convergent(2)
best
fel = abs(p/q - best)
"kedjebråkapprox fel", fel

for j in range(2,q):
    under = floor(r*j)
    over = under+1
    funder = abs(under/j - r)
    fover = abs(over/j - r)
    print(j,funder.n(),fover.n(),fel.n())
#+end_src

#+RESULTS:
#+begin_example
[0; 1, 58, 2]
58/59
('kedjebråkapprox fel', 1/7021)
2 0.483193277310924 0.0168067226890756 0.000142429853297251
3 0.316526610644258 0.0168067226890756 0.000142429853297251
4 0.233193277310924 0.0168067226890756 0.000142429853297251
5 0.183193277310924 0.0168067226890756 0.000142429853297251
6 0.149859943977591 0.0168067226890756 0.000142429853297251
7 0.126050420168067 0.0168067226890756 0.000142429853297251
8 0.108193277310924 0.0168067226890756 0.000142429853297251
9 0.0943043884220355 0.0168067226890756 0.000142429853297251
10 0.0831932773109244 0.0168067226890756 0.000142429853297251
11 0.0741023682200153 0.0168067226890756 0.000142429853297251
12 0.0665266106442577 0.0168067226890756 0.000142429853297251
13 0.0601163542340013 0.0168067226890756 0.000142429853297251
14 0.0546218487394958 0.0168067226890756 0.000142429853297251
15 0.0498599439775910 0.0168067226890756 0.000142429853297251
16 0.0456932773109244 0.0168067226890756 0.000142429853297251
17 0.0420168067226891 0.0168067226890756 0.000142429853297251
18 0.0387488328664799 0.0168067226890756 0.000142429853297251
19 0.0358248562582928 0.0168067226890756 0.000142429853297251
20 0.0331932773109244 0.0168067226890756 0.000142429853297251
21 0.0308123249299720 0.0168067226890756 0.000142429853297251
22 0.0286478227654698 0.0168067226890756 0.000142429853297251
23 0.0266715381804896 0.0168067226890756 0.000142429853297251
24 0.0248599439775910 0.0168067226890756 0.000142429853297251
25 0.0231932773109244 0.0168067226890756 0.000142429853297251
26 0.0216548157724628 0.0168067226890756 0.000142429853297251
27 0.0202303143479614 0.0168067226890756 0.000142429853297251
28 0.0189075630252101 0.0168067226890756 0.000142429853297251
29 0.0176760359316140 0.0168067226890756 0.000142429853297251
30 0.0165266106442577 0.0168067226890756 0.000142429853297251
31 0.0154513418270534 0.0168067226890756 0.000142429853297251
32 0.0144432773109244 0.0168067226890756 0.000142429853297251
33 0.0134963076139547 0.0168067226890756 0.000142429853297251
34 0.0126050420168067 0.0168067226890756 0.000142429853297251
35 0.0117647058823529 0.0168067226890756 0.000142429853297251
36 0.0109710550887021 0.0168067226890756 0.000142429853297251
37 0.0102203043379514 0.0168067226890756 0.000142429853297251
38 0.00950906678460858 0.0168067226890756 0.000142429853297251
39 0.00883430295195001 0.0168067226890756 0.000142429853297251
40 0.00819327731092437 0.0168067226890756 0.000142429853297251
41 0.00758352121336339 0.0168067226890756 0.000142429853297251
42 0.00700280112044818 0.0168067226890756 0.000142429853297251
43 0.00644909126441274 0.0168067226890756 0.000142429853297251
44 0.00592055003819710 0.0168067226890756 0.000142429853297251
45 0.00541549953314659 0.0168067226890756 0.000142429853297251
46 0.00493240774570698 0.0168067226890756 0.000142429853297251
47 0.00446987305560522 0.0168067226890756 0.000142429853297251
48 0.00402661064425770 0.0168067226890756 0.000142429853297251
49 0.00360144057623049 0.0168067226890756 0.000142429853297251
50 0.00319327731092437 0.0168067226890756 0.000142429853297251
51 0.00280112044817927 0.0168067226890756 0.000142429853297251
52 0.00242404654169360 0.0168067226890756 0.000142429853297251
53 0.00206120183922626 0.0168067226890756 0.000142429853297251
54 0.00171179582944289 0.0168067226890756 0.000142429853297251
55 0.00137509549274255 0.0168067226890756 0.000142429853297251
56 0.00105042016806723 0.0168067226890756 0.000142429853297251
57 0.000737136960047177 0.0168067226890756 0.000142429853297251
58 0.000434656621269197 0.0168067226890756 0.000142429853297251
59 0.000142429853297251 0.0168067226890756 0.000142429853297251
60 0.0165266106442577 0.000140056022408964 0.000142429853297251
61 0.0159801625568260 0.000413280066124811 0.000142429853297251
62 0.0154513418270534 0.000677690431011114 0.000142429853297251
63 0.0149393090569561 0.000933706816059757 0.000142429853297251
64 0.0144432773109244 0.00118172268907563 0.000142429853297251
65 0.0139625080801551 0.00142210730446025 0.000142429853297251
66 0.0134963076139547 0.00165520753756048 0.000142429853297251
67 0.0130440235795811 0.00188134955474727 0.000142429853297251
68 0.0126050420168067 0.00210084033613445 0.000142429853297251
69 0.0121787845573012 0.00231396906588722 0.000142429853297251
70 0.0117647058823529 0.00252100840336134 0.000142429853297251
71 0.0113622913954314 0.00272221564682211 0.000142429853297251
72 0.0109710550887021 0.00291783380018674 0.000142429853297251
73 0.0105905375848970 0.00310809255208933 0.000142429853297251
74 0.0102203043379514 0.00329320917556212 0.000142429853297251
75 0.00985994397759104 0.00347338935574230 0.000142429853297251
76 0.00950906678460858 0.00364882795223352 0.000142429853297251
77 0.00916730328495034 0.00381970970206264 0.000142429853297251
78 0.00883430295195001 0.00398620986856281 0.000142429853297251
79 0.00850973300712690 0.00414849484097436 0.000142429853297251
80 0.00819327731092437 0.00430672268907563 0.000142429853297251
81 0.00788463533561573 0.00446104367672995 0.000142429853297251
82 0.00758352121336339 0.00461160073785612 0.000142429853297251
83 0.00728966285309304 0.00475852991799129 0.000142429853297251
84 0.00700280112044818 0.00490196078431373 0.000142429853297251
85 0.00672268907563025 0.00504201680672269 0.000142429853297251
86 0.00644909126441274 0.00517881571233144 0.000142429853297251
87 0.00618178305805081 0.00531246981551241 0.000142429853297251
88 0.00592055003819710 0.00544308632543927 0.000142429853297251
89 0.00566518742328392 0.00557076763289585 0.000142429853297251
90 0.00541549953314659 0.00569561157796452 0.000142429853297251
91 0.00517129928894635 0.00581771170006464 0.000142429853297251
92 0.00493240774570698 0.00593715747168433 0.000142429853297251
93 0.00469865365501039 0.00605403451703262 0.000142429853297251
94 0.00446987305560522 0.00616842481673521 0.000142429853297251
95 0.00424590888987174 0.00628040689960195 0.000142429853297251
96 0.00402661064425770 0.00639005602240896 0.000142429853297251
97 0.00381183401195530 0.00649744433856017 0.000142429853297251
98 0.00360144057623049 0.00660264105642257 0.000142429853297251
99 0.00339529751294457 0.00670571258806553 0.000142429853297251
100 0.00319327731092437 0.00680672268907563 0.000142429853297251
101 0.00299525750894417 0.00690573259006573 0.000142429853297251
102 0.00280112044817927 0.00700280112044818 0.000142429853297251
103 0.00261075303907971 0.00709798482499796 0.000142429853297251
104 0.00242404654169360 0.00719133807369101 0.000142429853297251
105 0.00224089635854342 0.00728291316526611 0.000142429853297251
106 0.00206120183922626 0.00737276042492469 0.000142429853297251
107 0.00188486609597110 0.00746092829655227 0.000142429853297251
108 0.00171179582944289 0.00754746342981637 0.000142429853297251
109 0.00154190116413538 0.00763241076247013 0.000142429853297251
110 0.00137509549274255 0.00771581359816654 0.000142429853297251
111 0.00121129532894239 0.00779771368006662 0.000142429853297251
112 0.00105042016806723 0.00787815126050420 0.000142429853297251
113 0.000892392355172157 0.00795716516695174 0.000142429853297251
114 0.000737136960047177 0.00803479286451423 0.000142429853297251
115 0.000584581658750457 0.00811107051516259 0.000142429853297251
116 0.000434656621269197 0.00818603303390322 0.000142429853297251
117 0.000287294404941464 0.00825971414206708 0.000142429853297251
118 0.000142429853297251 0.00833214641788919 0.000142429853297251
#+end_example

* Slut