May 2023 - Challenge
This problem was suggested by Lorenzo Gianferrari Pini and Radu-Alexandru Todor - thanks!
Let x\in\mathbb{R}^n be a length n vector (x_0, x_1, \ldots, x_{n-1}) and A\in\mathbb{R}^{n\times n} be an n\times n matrix. We seek to compute the quadratic form x^TAx.
Assume x is equally spaced between -1 and 1, e.g., for n=5, we have
x = (-1, -0.5, 0, 0.5, 1)
The matrix A is generated in the following manner:
Let k\in\mathbb{N} be a natural number and define a vector a\in\mathbb{R}^{2^k} that is equally spaced between 0 and 1, i.e., a_t =\frac{t}{2^k-1} for t=0,1,\ldots,2^k-1. The values of A will be taken from the vector a in the following manner:
We are given a sequence Q_0, Q_1,\ldots, Q_{n-1}, with each Q_i\in\mathbb{N}^k being a vector of k natural numbers. Given two such vectors, define Q_i==Q_j as the binary vector of length k that has 1s in the entries that are equal in Q_i, Q_j and 0s in the other entries. Let [Q_i==Q_j] be the natural number whose binary representation is Q_i==Q_j, where the least significant bit is on index 0. For example, if
Q_i = (1, 5, 7, 8)
Q_j = (2, 5, 6, 8)
ThenQ_i==Q_j = (0, 1, 0, 1)
And[Q_i==Q_j] = 10 (since the vector (0, 1, 0, 1) stands for the binary representation 1010).
Now define A_{ij} = a_{[Q_i==Q_j]}.
So one can think of A_{ij} as taking on a value from a fixed list of 2^k values based on the "similarity" between Q_i and Q_j.
The values of the Q_i's are chosen pseudo-randomly using the formula
Q_i[t] = \left\lfloor2^k\cdot (\sin((i+1)\cdot (t+1))-\left\lfloor \sin((i+1)\cdot (t+1))\right\rfloor )\right\rfloor
For example, if k=5, then Q_{13}=(31, 8, 2, 15, 24)
Your goal: Find x^TAx (rounded to three decimals) for k=5, n=2^{20}.A bonus "*" will be given for finding x^TAx (rounded to three decimals) for k=5, n=2^{30}.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
01/05/2023 @ 15:30 PM EST
Solution:
05/06/2023 @ 12:00 PM EST
List Updated:
20/06/2023 @ 14:35 PM EST
People who answered correctly:
*Lazar Ilic(1/5/2023 4:26 PM IDT)
Lorenz Reichel(1/5/2023 6:25 PM IDT)
*Yan-Wu He(1/5/2023 10:24 PM IDT)
Amos Guler(2/5/2023 12:25 PM IDT)
*Alper Halbutogullari(2/5/2023 10:59 PM IDT)
*Bertram Felgenhauer(3/5/2023 1:49 PM IDT)
Dieter Beckerle(4/5/2023 5:52 PM IDT)
Sanandan Swaminathan(4/5/2023 5:55 PM IDT)
Julien Pradier(5/5/2023 5:27 PM IDT)
*Martin Thorne(5/5/2023 7:40 PM IDT)
Gary M. Gerken(6/5/2023 4:56 PM IDT)
*Li Li(7/5/2023 1:53 AM IDT)
Evan Semet(7/5/2023 3:26 AM IDT)
Philip Bui(7/5/2023 4:04 AM IDT)
*Harald Bögeholz(7/5/2023 8:05 AM IDT)
*Lawrence Au(7/5/2023 5:02 PM IDT)
Asaf Zimmerman(7/5/2023 6:14 PM IDT)
Lorenzo Gianferrari Pini(8/5/2023 12:29 PM IDT)
*Guy Daniel Hadas(8/5/2023 9:41 PM IDT)
*Peter Moser(9/5/2023 8:41 PM IDT)
Sachal Mahajan(10/5/2023 2:15 AM IDT)
Joram Meron(10/5/2023 12:58 PM IDT)
Stéphane Higueret(12/5/2023 7:21 AM IDT)
Daniel Chong Jyh Tar(12/5/2023 9:30 PM IDT)
Victor Chang(13/5/2023 5:04 AM IDT)
Michael Liepelt(13/5/2023 8:16 AM IDT)
*Dominik Reichl(13/5/2023 7:53 PM IDT)
*David F.H. Dunkley(14/5/2023 2:44 AM IDT)
*David Greer(14/5/2023 9:00 PM IDT)
Marco Bellocchi(16/5/2023 11:14 AM IDT)
*Daniel Chong Jyh Tar(16/5/2023 1:14 PM IDT)
*Tim Walters(16/5/2023 10:29 PM IDT)
*Andreas Stiller(17/5/2023 3:25 PM IDT)
Daniel Bitin(17/5/2023 6:50 PM IDT)
*Vladimir Volevich(18/5/2023 10:57 AM IDT)
*Dan Dima(18/5/2023 3:30 PM IDT)
Reda Kebbaj(19/5/2023 6:11 PM IDT)
*Bert Dobbelaere(19/5/2023 9:38 PM IDT)
*Daniel Copeland(21/5/2023 4:17 PM IDT)
*Daniel Mayer(21/5/2023 11:01 PM IDT)
Phil Proudman(22/5/2023 7:25 PM IDT)
*Hok Leung Nip(23/5/2023 8:10 PM IDT)
*Motty Porat(27/5/2023 3:21 AM IDT)
*Reiner Martin(27/5/2023 6:14 PM IDT)
Shouky Dan & Tamir Ganor(29/5/2023 11:56 AM IDT)
Latchezar Christov(30/5/2023 1:23 PM IDT)
*Diane Pham(31/5/2023 12:07 PM IDT)
*Kang Jin Cho(31/5/2023 7:51 PM IDT)
*Balakrishnan V(1/6/2023 5:48 AM IDT)
Nyles Heise(1/6/2023 7:56 PM IDT)
Matt Cristina(2/6/2023 12:55 AM IDT)
*Vaskor Basak(2/6/2023 2:52 PM IDT)