text:
# Noel Hush

Noel Sydney Hush (15 December 1924 – 20 March 2019)[1] was an Australian chemist at the University of Sydney.[2][3]

Noel Hush
Hush in 2006
Born
Noel Sydney Hush

15 December 1924
Died20 March 2019 (aged 94)
NationalityAustralian
CitizenshipAustralia, United Kingdom
Known forelectron transfer, molecular electronics, finite-field response
AwardsFellow of the Royal Society (FRS) (1988)

Centenary Medal of the Royal Society of Chemistry (1988)
Welch Award (1988)
2011 Foreign Associate of the National Academy of Sciences of USA (2011)

2014 Ahmed Zewail Prize for Molecular Science (2014)
Scientific career
FieldsTheoretical chemistry, chemical physics
InstitutionsUniversity of Manchester, University of Bristol, University of Sydney
ThesisThe electronic spectrum of pentacene in five states of ionization: theory and experiment
Doctoral advisors(D.Sc. 1959) H.C. Longuet-Higgins FRS and M.H.L. Pyrce FRS

## Career

Hush was born in Sydney on 15 December 1924 and obtained his degrees (BSc Hons (1945) and MSc (1948)) at the University of Sydney, where he worked as a Research Fellow in the Department of Chemistry (1945–49). He then accepted an invitation from M. G. Evans FRS to work in England as an Assistant Lecturer at the University of Manchester (1950–54) in the department created by Michael Polanyi. He was subsequently Lecturer and then Reader in the Department of Chemistry at the University of Bristol (1955–71).

He then returned to Australia in 1971 to found The Department of Theoretical Chemistry at the University of Sydney, the first such department in Australia. This rapidly became established as a centre for excellence in teaching, from undergraduate to postdoctoral level, and research. In 1989 he became Emeritus Professor engaged in full-time research. He has also held numerous prestigious visiting scientist positions at universities in Australia, the United Kingdom and the United States of America.[2]

A unifying theme of Hush’s research is elucidation of chemical electron transfer. This is the basis of oxidation-reduction processes, which are ubiquitous in Nature in both the inorganic and biological spheres. The mechanism of these reactions - the simplest of which proceed without making or breaking chemical bonds - remained unknown until the mid nineteen-fifties, when several independent theoretical studies showed that it was due to modulation of coupling between electronic and vibrational motions. According to his Royal Society election citation,[4] Hush’s research in the area of homogeneous and heterogeneous electron transfer[5] showed that electron transfer occurring during a collision between a molecule and either another molecule or else an electrode surface occurs adiabatically on a continuous potential-energy surface, and that electron transfer can occur by either optical or thermal mechanisms with the corresponding rates being closely connected.[6]

Fig. 1. Electron transfer occurs between donor (D) and acceptor (A) species separated by distance R that may be found in many forms in both condensed phases and the gas phase. Internal structure, external structure, or chance collisions provide interconnection between the species. Upon electron transfer, the structure of the local chemical environments involving D and A change, as does the polarization these species induce on any surrounding media.

Figure 1 sketches the basic elements of adiabatic electron-transfer theory. Two chemical species (ions, molecules, polymers, protein cofactors, etc.) labelled D (for “donor”) and A (for “acceptor”) become a distance R apart, either through collisions, covalent bonding, location in a material, protein or polymer structure, etc. These species have different chemical bonding environments and they polarize any surrounding condensed media. A key feature is that both species must be able to sustain different charge (valence) states. Electron-transfer theories specify equations describing the rate of charge transfer processes that utilize these different charged states. All electrochemical reactions occur by this mechanism. Adiabatic electron-transfer theory stresses that intricately coupled to such charge transfer is the ability of any D-A system to absorb or emit light. Hence fundamental understanding of any electrochemical process demands simultaneous understanding of the optical processes that the system can undergo.

Fig. 2. When the donor species absorbs light energy, it goes into a high-energy excited state, generating significant changes to its local chemical environment and the polarization of its external environment. These environments facilitate coupling ${\displaystyle V_{DA}}$  between the donor and acceptor, which drives photochemical charge separation with a rate given by Eqn. (3) in the weak-coupling limit. This rate is also dependent on the energy ${\displaystyle \lambda }$  required to rearrange the atoms to the preferred local geometry and environment polarization of the charge-separated state D+-A and the energy change ${\displaystyle \Delta G_{0}}$  associated with charge separation.

Figure 2 sketches what happens if light is absorbed by just one of the chemical species, taken to be the charge donor. This produces an excited state of the donor. As the donor and acceptor are close to each other and surrounding matter, they experience a coupling ${\displaystyle V_{DA}}$ . If the free energy change ${\displaystyle \Delta G_{0}}$  is favorable, this coupling facilitates primary charge separation to produce D+-A ,[1] producing charged species. In this way, solar energy is captured and converted to electrical energy. This process is typical of natural photosynthesis as well as modern organic photovoltaic and artificial photosynthesis solar-energy capture devices.[7] The inverse of this process is also used to make organic light-emitting diodes (OLEDs).

Fig. 3. Light energy is absorbed by the donor and acceptor, initiating intervalence charge transfer to directly convert solar energy into electrical energy as D+-A. In the weak-coupling limit, the coupling ${\displaystyle V_{DA}}$ , reorganization energy ${\displaystyle \lambda }$ , and the free energy change ${\displaystyle \Delta G_{0}}$  control the rate of light absorption (and hence charge separation) via Eqn. (1).

Unifying standard electrochemical electron-transfer processes with this type of solar energy harvesting, adiabatic electron-transfer theory also depicts a third application in which the donor and acceptor are both involved in light absorption, as sketched in Figure 3. Here, light absorption directly leads to charge separation D+-A . Hush’s theory for this process[6] considers the donor-acceptor coupling ${\displaystyle V_{DA}}$ , the energy ${\displaystyle \lambda }$  required to rearrange the atoms from their initial geometry to the preferred local geometry and environment polarization of the charge-separated state, and the energy change ${\displaystyle \Delta G_{0}}$  associated with charge separation. In the weak-coupling limit ( ${\displaystyle 4V_{DA}^{2}/\lambda ^{2}\ll 1}$ ), Hush showed[6] that the rate of light absorption (and hence charge separation) is given from the Einstein equation by

${\displaystyle k\propto {\frac {V_{DA}^{2}R^{2}}{\lambda +\Delta G_{0}}}.}$  … (1)

This theory explained[6] how the worlds first modern synthetic dye, Prussian blue absorbes light, creating[8][9][10][11][12] the field of intervalence charge transfer spectroscopy.

Hush’s theory also provides theoretical underpinning for the Robin-Day classification system[13] for mixed-valence systems. Mixed valence is widespread in chemistry, from superconductors to minerals, magnetic molecular clusters and enzymes. It occurs when the same chemical species is found in two formally different oxidation states in the same system.[14]

The synthesis of the mixed-valence Creutz-Taube ion, an event leading significantly to the award of the 1983 Nobel Prize in Chemistry to Henry Taube, demonstrated the successfulness of adiabatic electron-transfer theory. In this molecule, the coupling ${\displaystyle V_{DA}}$  is not small, delivering unprecedented chemical phenomena in which charge is not localized on just one chemical species but is shared quantum mechanically between two, presenting classically forbidden half-integral valence states. Hush showed[15] that the critical requirement for this phenomenon is

${\displaystyle {\frac {2|J_{DA}|}{\lambda }}\geq 1.}$  … (2)

Adiabatic electron-transfer theory stems from London’s approach to charge-transfer and indeed general chemical reactions[16] applied by Hush using parabolic potential-energy surfaces.[17][18] Hush himself has carried out many theoretical and experimental studies of mixed valence complexes and long range electron transfer in biological systems. Hush’s quantum-electronic adiabatic approach to electron transfer was unique; directly connecting with the Quantum Chemistry concepts of Mulliken, it forms the basis of all modern computational approaches to modeling electron transfer.[19][20][21][22][23] Its essential feature is that electron transfer can never be regarded as an “instantaneous transition”; instead, the electron is partially transferred at all molecular geometries, with the extent of the transfer being a critical quantum descriptor of all thermal, tunneling, and spectroscopic processes. It also leads seamlessly[24] to understanding electron-transfer transition-state spectroscopy pioneered by Zewail.

In adiabatic electron-transfer theory, the ratio ${\displaystyle 2V_{DA}/\lambda }$  is of central importance. In the very strong coupling limit when Eqn. (2) is satisfied, intrinsically quantum molecules like the Crautz-Taube ion result. Most intervalence spectroscopy occurs in the weak-coupling limit described by Eqn. (1), however. In both natural photosynthesis and in artificial solar-energy capture devices, ${\displaystyle 2V{_{D}A}/\lambda }$  is maximized by minimiming ${\displaystyle \lambda }$  through use of large molecules like chlorophylls, pentacenes, and conjugated polymers. The coupling ${\displaystyle V_{DA}}$  can be controlled by controlling the distance R at which charge transfer occurs- the coupling typically decreases exponentially with distance. When electron transfer occurs during collisions of the D and A species, the coupling is typically large and the “adiabatic” limit applies in which rate constants are given by transition state theory.[5] However, in biological applications as well as modern organic conductors and other device materials, R is externally constrained and so the coupling set at low or high values. In these situations, weak-coupling scenarios often become critical.

In the weak-coupling (“non-adiabatic”) limit, the activation energy for electron transfer is given by the expression derived independently by Kubo and Toyozawa[25] and by Hush.[18] Using adiabatic electron-transfer theory,[26] in this limit Levich and Dogonadze then determined the electron-tunneling probability to express the rate constant for thermal reactions as[27]

${\displaystyle k={\frac {2\pi V_{DA}^{2}}{\hbar (4\pi \lambda k_{\beta }T)^{1/2}}}\exp {\frac {-(\Delta G_{0}+\lambda )^{2}}{4\lambda k_{\beta }T}}}$ . … (3)

This approach is widely applicable to long-range ground-state intramolecular electron transfer, electron transfer in biology, and electron transfer in conducting materials. It also typically controls the rate of charge separation in the excited-state photochemical application described in Figure 2 and related problems.

Marcus showed[28] that the activation energy in Eqn. (3) reduces to ${\displaystyle \lambda /4}$  in the case of symmetric reactions with ${\displaystyle \Delta G_{0}=0}$ . In that work,[28] he also derived what is the standard expression for the solvent contribution to the reorganization energy, making the theory readily applicable to practical problems. Use of this solvation description (instead[5] of the form that Hush originally proposed[18]) in approaches spanning the adiabatic and non-adiabatic limits is often termed “Marcus-Hush Theory”.[20][21][29][30] These and other contributions, including the widespread demonstration of the usefulness of Eqn. (3),[31] led to the award of the 1992 Nobel Prize in Chemistry to Marcus.

Adiabatic electron-transfer theory is often also widely applied [2] in Molecular Electronics. In recent years it has been generalized to arbitrary chemical reactions, providing a single conceptual basis covering many different aspects of chemical research.[32] In particular, this reconnects adiabatic electron-transfer theory with its roots in proton-transfer theory[33] and hydrogen-atom transfer,[17] leading back to London’s theory of general chemical reactions.[16] In this approach, most chemical processes can be depicted in terms of the three critical parameters ${\displaystyle V_{DA}}$ , ${\displaystyle \lambda }$  and ${\displaystyle \Delta G_{0}}$ , with for example the resonance energy that makes benzene and all aromatic compounds unique being nothing other than ${\displaystyle V_{DA}}$ .[32] This approach also leads to a simple explanation in terms of the orbital Rydbergization processes discovered by Mulliken as to why first-row elements like nitrogen have bond angles around the tetrahedral angles while later-row elements have very much larger angles.[34] Adiabatic electron-transfer theory applied in a simple one-dimensional form also provides analytical or numerically exact solutions for chemical processes not involving conical intersections, providing critical testbeds for examining failure of the Born-Oppenheimer approximation that is fundamental to chemical understanding.[35] Similarly, it provides a basis for classifying the usefulness of general chemical reactions for applications as qubits in quantum information processors.[36]

## References

1. ^ "Passing of eminent scientist Professor Noel Hush". University of Sydney. 22 March 2019. Retrieved 22 March 2019.
2. ^ a b "Hush, Noel Sydney (1924 - )". Encyclopaedia of Australian Science. Retrieved 18 September 2015.
3. ^ Faculty of Science - The University of Sydney
4. ^ "Fellows Details". Royal Society. Retrieved 18 September 2015.
5. ^ a b c Hush, N. S. (1961). "Adiabatic theory of outer-sphere electron-transfer processes in solution". Trans. Faraday Soc. 57: 577. doi:10.1039/TF9615700557.
6. ^ a b c d Hush, N. S. (1967). "Intervalence-transfer absorption. II. Theoretical considerations and spectroscopic data". Prog. Inorg. Chem. Progress in Inorganic Chemistry. 8: 391–444. doi:10.1002/9780470166093.ch7. ISBN 9780470166093.
7. ^ Warman, J. M.; Haas, M. P. d.; Paddon-Row, M. N.; Cotsaris, E.; Hush, N. S.; Oevering, H.; Verhoeven, J. W. (1986). "Light-induced giant dipoles in simple model compounds for photosynthesis". Nature. 320 (6063): 615–616. Bibcode:1986Natur.320..615W. doi:10.1038/320615a0.CS1 maint: Multiple names: authors list (link)
8. ^ Nelsen, S. F.; Ismagilov, R. F.; Trieber, D. A. (1997). "Adiabatic Electron Transfer: Comparison of Modified Theory with Experiment". Science. 278 (5339): 846–849. Bibcode:1997Sci...278..846N. doi:10.1126/science.278.5339.846.CS1 maint: Multiple names: authors list (link)
9. ^ German, E. D. (1979). "Intramolecular intervalence charge transfer in bimolecular mixed-valence complexes of metals". Chem. Phys. Lett. 64 (2): 295–298. Bibcode:1979CPL....64..295G. doi:10.1016/0009-2614(79)80516-3.
10. ^ Sun, D. L.; Rosokha, S. V.; Lindeman, S. V.; Kochi, J. K. (2003). "Intervalence (Charge-Resonance) Transitions in Organic Mixed-Valence Systems. Through-Space versus Through-Bond Electron Transfer between Bridged Aromatic (Redox) Centers". J. Am. Chem. Soc. 125 (51): 15950–15963. doi:10.1021/ja037867s. PMID 14677987.CS1 maint: Multiple names: authors list (link)
11. ^ Nelsen, S. F.; Weaver, M. N.; Luo, Y.; Lockard, J. V.; Zink, J. I. (2006). "Use of the neighboring orbital model for analysis of electronic coupling in Class III intervalence compounds". Chem. Phys. 324 (1): 195–201. Bibcode:2006CP....324..195N. doi:10.1016/j.chemphys.2006.01.023.CS1 maint: Multiple names: authors list (link)
12. ^ Rosokha, S. V.; Kochi, J. K. (2008). "Fresh Look at Electron-Transfer Mechanisms via the Donor/Acceptor Bindings in the Critical Encounter Complex". Acc. Chem. Res. 41 (5): 641–653. doi:10.1021/ar700256a. PMID 18380446.CS1 maint: Multiple names: authors list (link)
13. ^ Robin, M. B.; Day, P. (1967). "Mixed Valence Chemistry-A Survey and Classification". Adv. Inorg. Chem. Radiochem. Advances in Inorganic Chemistry and Radiochemistry. 10: 247–422. doi:10.1016/S0065-2792(08)60179-X. ISBN 9780120236107.CS1 maint: Multiple names: authors list (link)
14. ^ Day, P.; Hush, N. S.; Clark, R. J. H. (2008). "Mixed valence: origins and developments". Phil. Trans. Roy. Soc. A. 366: 5. doi:10.1098/rsta.2007.21.35 (inactive 2019-03-10).CS1 maint: Multiple names: authors list (link)
15. ^ Hush, N. S. (1975). "Inequivalent XPS [x-ray photoelectron spectroscopy] binding energies in symmetrical delocalized mixed-valence complexes". Chem. Phys. 10 (2–3): 361–366. Bibcode:1975CP.....10..361H. doi:10.1016/0301-0104(75)87049-2.
16. ^ a b London, F. (1932). "On the theory of non-adiabatic chemical reactions". Z. Phys. World Scientific Series in 20th Century Chemistry. 74: 32–60. doi:10.1142/9789812795762_0003. ISBN 978-981-02-2771-5.
17. ^ a b Hush, N. S. (1953). "Quantum-mechanical discussion of the gas phase formation of quinonedimethide monomers". J. Polymer Sci. 11 (4): 289–298. Bibcode:1953JPoSc..11..289H. doi:10.1002/pol.1953.120110401.
18. ^ a b c Hush, N. S. (1958). "Adiabatic rate processes at electrodes". J. Chem. Phys. 28 (5): 962–972. Bibcode:1958JChPh..28..962H. doi:10.1063/1.1744305.
19. ^ Kornyshev, A. A.; Tosi, M.; Ulstrup, J. (1997). Electron and Ion Transfer in Condensed Media. Singapore: World Scientific. ISBN 978-9810229290.CS1 maint: Multiple names: authors list (link)
20. ^ a b Kuznetsov, A.; Ulstrup, J. (1998). Electron Transfer in Chemistry and Biology: An introduction to the theory. Chichester: Wiley. ISBN 978-0-471-96749-1.CS1 maint: Multiple names: authors list (link)
21. ^ a b Devault, D. (1980). "Quantum mechanical tunnelling in biological systems". Q. Rev. Biophys. 13 (4): 387–564. doi:10.1017/S003358350000175X. PMID 7015406.
22. ^ Cave, R. J.; Newton, M. D. (1996). "Generalization of the Mulliken-Hush treatment for the calculation of electron transfer matrix elements". Chem. Phys. Lett. 249 (1–2): 15–19. Bibcode:1996CPL...249...15C. doi:10.1016/0009-2614(95)01310-5.CS1 maint: Multiple names: authors list (link)
23. ^ "Electrochemical Society Millennial Survey". Interface. 9: 20. 2000.
24. ^ Reimers, J. R.; Hush, N. S. (2017). "Relating transition-state spectroscopy to standard chemical spectroscopic processes". Chem. Phys. Lett. 683: 467–477. Bibcode:2017CPL...683..467R. doi:10.1016/j.cplett.2017.04.070.CS1 maint: Multiple names: authors list (link)
25. ^ Kubo, R.; Toyozawa, Y. (1955). "Application of the Method of Generating Function to Radiative and Non-Radiative Transitions of a Trapped Electron in a Crystal". Prog. Theor. Phys. 13 (2): 160–182. Bibcode:1955PThPh..13..160K. doi:10.1143/PTP.13.160.CS1 maint: Multiple names: authors list (link)
26. ^ Levich, V. G.; Dogonadze, R. R. (1960). "Adiabatic theory for electron-transfer processes in solution". Proc. Akad. Naukl. SSSR. 133: 591.CS1 maint: Multiple names: authors list (link)
27. ^ Levich, V. G.; Dogonadze, R. R. (1959). "Theory of rediationless electron transitions between ions in solution". Proc. Akad. Naukl. SSSR. 29: 9.CS1 maint: Multiple names: authors list (link)
28. ^ a b Marcus, R. A. (1956). "On the Theory of Oxidation-Reduction Reactions Involving Electron Transfer. 1". J. Chem. Phys. 24 (5): 966–978. Bibcode:1956JChPh..24..966M. doi:10.1063/1.1742723.
29. ^ Schmickler, W. Electron transfer and single molecule events (PDF). Paris: Eolss Publishers.
30. ^ Efrima, S.; Bixon, M. (1976). "Vibrational effects in outer-sphere electron-transfer reactions in polar media". Chem. Phys. 13 (4): 447–460. Bibcode:1976CP.....13..447E. doi:10.1016/0301-0104(76)87014-0.CS1 maint: Multiple names: authors list (link)
31. ^ Marcus, R. A.; Sutin, N. (1985). "Electron transfers in chemistry and biology". Biochim. Biophys. Acta. 811 (3): 265–322. doi:10.1016/0304-4173(85)90014-x.CS1 maint: Multiple names: authors list (link)
32. ^ a b Reimers, J. R.; McKemmish, L.; McKenzie, R. H.; Hush, N. S. (2015). "A unified diabatic description for electron transfer reactions, isomerization reactions, proton transfer reactions, and aromaticity". Phys. Chem. Chem. Phys. 17 (38): 24598–24617. Bibcode:2015PCCP...1724598R. doi:10.1039/C5CP02236C. PMID 26193994.CS1 maint: Multiple names: authors list (link)
33. ^ Horiuti, J.; Polanyi, M. (1935). "Outlines of a theory of proton transfer". Acta Physicochimica U.R.S.S. 2 (1–2): 185–197. doi:10.1016/s1381-1169(03)00034-7.CS1 maint: Multiple names: authors list (link)
34. ^ Reimers, J. R.; McKemmish, L.; McKenzie, R. H.; Hush, N. S. (2015). "Bond angle variations in XH3 [X=N,P,As,Sb,Bi]: the critical role of Rydberg orbitals exposed using a diabatic state model". Phys. Chem. Chem. Phys. 17 (38): 24618–24640. Bibcode:2015PCCP...1724618R. doi:10.1039/C5CP02237A. PMID 26190514.CS1 maint: Multiple names: authors list (link)
35. ^ Reimers, J. R.; McKemmish, L.; McKenzie, R. H.; Hush, N. S. (2015). "Non-adiabatic effects in thermochemistry, spectroscopy and kinetics: the general importance of all three Born-Oppenheimer breakdown corrections". Phys. Chem. Chem. Phys. 17 (38): 24641–24665. Bibcode:2015PCCP...1724641R. doi:10.1039/C5CP02238J. PMID 26196265.CS1 maint: Multiple names: authors list (link)
36. ^ McKemmish, L. K.; McKenzie, R. H.; Hush, N. S.; Reimers, J. R. (2011). "Quantum entanglement between electronic and vibrational degrees of freedom in molecules". J. Chem. Phys. 135 (24): 244110. arXiv:1107.1105. Bibcode:2011JChPh.135x4110M. doi:10.1063/1.3671386. PMID 22225147.CS1 maint: Multiple names: authors list (link)


text:
# A multiple of n in every base!

In November 2019, Alon Ran published a particularly lovely sequence in the OEIS, A329126:

$$\a(n)\$$ is the lexicographically earliest string of digits which yields a multiple of $$\n\$$ when read in any numeric base. 1, 110, 101010, 111100, 100010001000100010, 1111110, 10000010000010000010000010000010000010, 11111111000, 1010101010101010100, ...

For example, $$\a(3) = 101010\$$ because this is the smallest number that is a multiple of $$\3\$$ in every integer base \begin{alignat}{2} 101010_1 &= 1^5 + 1^3 + 1^1 = 3 &&= 3\cdot1 \\ 101010_2 &= 2^5 + 2^3 + 2^1 = 42 &&= 3\cdot14 \\ 101010_3 &= 3^5 + 3^3 + 3^1 = 273 &&= 3\cdot91 \\ 101010_4 &= 4^5 + 4^3 + 4^1 = 1092 &&= 3\cdot364 \\ 101010_5 &= 5^5 + 5^3 + 5^1 = 3255 &&= 3\cdot1085 \\ &\hspace{0.4em}\vdots \end{alignat} Another way of conceptualizing this is that the polynomial $$\f(n) = n^5 + n^3 + n\$$ is divisible by $$\3\$$ for every integer $$\n\$$, which you can check manually with modular arithmetic.

We can generalize this idea further by looking at polynomials with restricted coefficients. For example, if we allow the coefficients of the polynomial to be $$\\{-1,0,1\}\$$, then $$\g(n) = n^4-n^2\$$ is divisible by $$\4\$$ for all integers $$\n\$$.

## The challenge!

In any reasonable format of your choosing, you will be given a list of allowed integer coefficients, coefficients (which always contains both $$\0\$$ and $$\1\$$), and a positive integer, k.

Your job is to find the degree, d, of the smallest monic polynomial as measured by degree, $$p(n) = n^d + c_{d-1}n^{d-1} + \dots + c_2n^2 + c_1n + c_0,$$ such that each $$\c_i\$$ is in coefficients and $$\p(n)\$$ is a multiple of $$\k\$$ for all integers $$\n \in \mathbb{Z}\$$.

In order to avoid the simplest form of brute-forcing, your program must be able to compute each individual test case from the test data on TIO (or, if TIO does not support your language, on my machine within 60 seconds). This is , so shortest code wins.

## Test data

coefficients | k | d  | example
-------------+---+----+--------------------------------------------
[0,1]        | 1 | 0  | 1
[0,1]        | 2 | 2  | x^2  + x
[0,1]        | 3 | 5  | x^5  + x^3  + x
[0,1]        | 4 | 5  | x^5  + x^4  + x^3  + x^2
[0,1]        | 5 | 17 | x^17 + x^13 + x^9  + x^5  + x
[0,1]        | 6 | 6  | x^6  + x^5  + x^4  + x^3  + x^2  + x
[0,1]        | 7 | 37 | x^37 + x^31 + x^25 + x^19 + x^13 + x^7 + x
[-1,0,1]     | 4 | 4  | x^4  - x^2
[-1,0,1]     | 5 | 5  | x^5  - x
[-1,0,1]     | 6 | 3  | x^3  - x
[-1,0,1]     | 7 | 7  | x^7  - x
[-1,0,1]     | 8 | 5  | x^5  - x^3
[-1,0,1]     | 9 | 8  | x^8  - x^6  - x^4 + x^2
[ 0,1,2]     | 4 | 4  | x^4  + x^2  + 2x
[ 0,1,3]     | 5 | 9  | x^9  + x^5  + 3x
[ 0,1,2,3]   | 6 | 3  | x^3  + 3x^2 + 2x

• "Your job is to find the degree, d, of the smallest monic polynomial" Not sure how "smallest polynomial" is defined here. Does it refer to the smallest degree of any monic polynomial satisfying the conditions? Jun 18, 2021 at 19:56
• Yep! As measured by degree—I updated the post to disambiguate. Jun 18, 2021 at 19:57
• Your challenges are always so cool Jun 18, 2021 at 21:23
• 60 per test case is fine. I've updated the challenge to reflect this. Jun 19, 2021 at 5:55
• wshould optimization compiler flags count towards the total byte count? Jun 19, 2021 at 9:48

# Python 3.8+, 385 372 bytes

from itertools import*
E=enumerate
def f(c,k):
p=[range(k)]
while(n:=[a*b%k for a,b in E(p[-1])])not in p:p+=n,;S=[{0}];M=[D:=0]*len(p)
for d in range(k*k):
if[]==p[D:]:D=p.index(n)
if any(all(sum(s)%k<1for s in zip(*T))for T in product(*[[[P*(C+(i==D))for P in p[i]]for C in S[r]]for i,r in E(M)])):return(k!=1)+d
S+=[{a+b for b in S[-1]for a in c}];M[D]+=1;D+=1

Try it online!

This code is surprisingly fast and runs in only about 1.5s on TIO.

-12 bytes thanks to @ovs

Python 3.8+ is used for the walrus operator (:=), but it costs three bytes because Python 3 doesn't allow mixed tabs and spaces.

## How

A naive way to go about the challenge is to test all possible coefficient combinations at a given degree, then proceed to the next degree. This is viable for all of the test cases except for [0,1] | 7, which requires degree d=37. This would require brute-forcing more than 2^37 combinations, even if the order is chosen intelligently.

My next approach was to work out what possible sums could be obtained for each n then work backwards on sets of coefficients which work for those sums, but that ran into much of a similar problem.

Since only that one test case fails, it would be possible to optimize for coeffs=[0,1] specifically, but that seems too cheaty / against the spirit of the challenge.

The method used in this answer relies on the property that the powers of n (mod k) are periodic, at least after a certain point. As an example for k=4:

Table of n^i mod k for k=4
i=0 corresponds to the constant term

n\i 0 1 2 3 4 5 6 7 8 9
0   1 0 0 0 0 0 0 0 0 0
1   1 1 1 1 1 1 1 1 1 1
2   1 2 0 0 0 0 0 0 0 0
3   1 3 1 3 1 3 1 3 1 3

Thus the powers mod 4 overall have a period of length 2 starting from i=1. (Note that i=0 is never a solution unless k=1, and the constant term should always be divisible by k, so it should normally be zero).

We use this periodicity to our advantage. For example, in the [0,1] | 7 | 37 case, we don't need to consider 37 exponents. The powers have a period of length 6 starting from i=0, so there are only 6 distinct tuples of residues of of powers.

Table of n^i mod k for k=7
i=0 corresponds to the constant term

n\i 1 2 3 4 5 6  7 8 9
0   0 0 0 0 0 0  0 0 0
1   1 1 1 1 1 1  1 1 1
2   2 4 1 2 4 1  2 4 1
3   3 2 6 4 5 1  3 2 6
4   4 2 1 4 2 1  4 2 1
5   5 4 6 2 3 1  5 4 6
6   6 1 6 1 6 1  6 1 6

We only need to consider the coefficients with which to weight the six columns i∊[1...6]. Now we have to be careful. The coefficients are not just chosen from [0,1]. As we proceed to higher degrees, we can reuse the coefficients, so for example the n term is the same as the n^7 term is the same as the n^13 term; these all have powers in the 1 column. Thus we can use 7 copies of the 1 column to obtain the desired polynomial.

## Ungolfed Code

import itertools

def min_degree(coeffs, k):
if k == 1:
return 0
# powers[n-1] will be the tuple of [1...k]^m mod k
# e.g. for k=4, powers=[(1,2,3),(1,0,1),(1,0,3)]; next power will be (1,0,1) which repeats
powers = [tuple(range(1, k))]
# keep computing more powers until two are the same,
# (we know the sequence of powers must be periodic eventually)
while (
next_power := tuple([a * b % k for a, b in enumerate(powers[-1], 1)])
) not in powers:
powers.append(next_power)
# period_start_index is 0-indexed
# for k=4, period_start_index=1 and period_length=2
period_start_index = powers.index(next_power)
period_length = len(powers) - period_start_index
# summed_coeffs[i] is all possibilities of sums of i coeffs with replacement.
# for example for i=2 and coeffs=[0,1,3], summed_coeffs[i]={0,1,2,3,4,6}={0+0,0+1,1+1,0+3,1+3,3+3}
summed_coeffs = [{0}]
for i in range(k * k):
# mod by k here is unnecessary but can theoretically improve speed
summed_coeffs.append({(a + b) % k for b in summed_coeffs[-1] for a in coeffs})
max_repeats = [0 for _ in powers]
# A simple upper bound for d is d ≤ k*φ(k)
# because Σ_{m=1}^{k}(n^(mφ(k)) always works
# Since φ(k) ≤ k-1, we know d ≤ k*φ(k) ≤ k*(k-1) < k*k
for d in range(1, k * k):
# degree_index is the index of [1...n]^(d-1) mod k in the list powers
# we use d-1 because the d-th coefficient must be 1 ∵ monic polynomial
degree_index = (
d - 1
if d - 1 < period_start_index
else period_start_index + (d - 1 - period_start_index) % period_length
)
possible_column_totals = [
[
tuple(
[p * (coeff + (1 if i == degree_index else 0)) for p in powers[i]]
)
for coeff in summed_coeffs[r]
]
for i, r in enumerate(max_repeats)
]
max_repeats[degree_index] += 1
for column_totals in itertools.product(*possible_column_totals):
if all(sum(s) % k == 0 for s in zip(*column_totals)):
return d

• 373 bytes with a few minor golfs. (Footer removed to fit the link in a comment)
– ovs
Jun 20, 2021 at 6:34
• @ovs Nice finds. I was so confused with the p+=n,, thinking it was the JS comma operator, but that led me to an extra byte save. Jun 20, 2021 at 7:34

import Data.Set
k%g|w<-fromList.fmap(\q->(modk).sum.zipWith(*)q.(<$>[1..]).(^)<$>[1..k]).mapM id=[n|n<-[0..],t<-[div n 2],n>(k-1)^2||size(intersection(w$(0-)<$>g<$[1..t])$w$([0]<$[1..t])++(g<$[1..n-t-1])++[[1]])>0]!!0  Use compiler flags -O2 (I didn't test if -O is enough. It might be) To get the result, evaluate k%digits, e.g, 6%[0,1]. Here's a link to TIO with a main function that runs all the tests, except 7%[0,1]: Try it online! The code works by generating all the negations of the possible first halves of the polynomial, and all the possible second halves of the polynomial. Then it evaluates all of them mod k at all possible inputs, puts the results in two sets, and checks if they have any intersection. It also has two spot optimizations: the constant coefficient is always zero, and a polynomial of degree k^2-2k+2 is always possible. The code doesn't run to completion on the TIO site. however, it reached 30s on my computer. So I'm waiting for the OP to decide if this program is ok. Also, there is a slightly shorter but less performant version that also might make the cut: import Data.Set k%g|w<-fromList.fmap(\q->(modk).sum.zipWith(*)q.(<$>[1..]).(^)<$>[1..k]).mapM id=[n|n<-[0..],t<-[div n 2],size(intersection(w$(0-)<$>g<$[1..t])$w$([0]<$[1..t])++(g<$[1..n-t-1])++[[1]])>0]!!0

that removes the k^2-2k+2 optimization.

# JavaScript (ES6),  297 290 286  284 bytes

Expects (coefficients)(k).

c=>k=>(g=(i,q,d,A,m,h)=>i<n?c.map(c=>c*q&&i>=r|!m&&g(i,q-1,(D=m-~i)>d?D:d,A.map((v,j)=>v+B[i][j]*c),m+n-r,D>d?c:h),g(i+1,q,d,A,0,h)):M=h^!A.some(x=>x%k)|M<d?M:d)(0,k,0,(M=A=>(r=M[A+A])?A.fill(!r--):M(A.map((v,i)=>v*i%k),M[A+A]=n=B.push(A)))([...Array(k)].map((_,i)=>i),B=[]),0)&&M^k<2

Try it online!

## Commented

I think this is very close to @fireflame241's solution, although I came up with this independently. The first part was working fine from the beginning. But for some reason, I got the second part poorly written and very slow on my early attempts.

### Step 1

We store in $$\B[\:]\$$ all the distinct tuples $$\(0,1,\dots,k-1)\$$ raised to increasing powers, modulo $$\k\$$. At the end of the process, $$\n\$$ is the number of entries in $$\B[\:]\$$ and $$\r\$$ is the 0-based index at which the sequence restarts.

( M = A =>            // M is a recursive function taking a vector A[]
(r = M[A + A]) ?    // if A[] was already encountered at index r:
A.fill(!r--)      //   stop the recursion, clear all values in A[]
//   and decrement r
:                   // else:
M(                //   do a recursive call:
A.map((v, i) => //     update each value in A[] ...
v * i % k     //       ... to the next power modulo k
),              //     end of map()
M[A + A] = n =  //     store A[] in M, set n = length of B[] ...
B.push(A)       //     ... once A[] has been appended to B[]
)                 //   end of recursive call
)(                    // initial call to M with:
[...Array(k)]       //   an array filled with all values from 0 to k - 1
.map((_, i) => i),  //
B = []              //   initialize B[] to an empty array
)                     //

### Step 2

We now use a recursive function $$\g\$$ to find a combination of tuples from $$\B[\:]\$$ multiplied by some coefficients from $$\c[\:]\$$ that sum up to $$\0\$$'s modulo $$\k\$$. We eventually return the lowest degree $$\M\$$ of the corresponding polynomials, ignoring those that are not monic.

By using any tuple that repeats, it's always possible to build a solution with exactly $$\k\$$ terms that lead to the same result modulo $$\k\$$. That's why we use $$\k\$$ as an upper bound for the number of terms in the polynomial.

The initial call to $$\g\$$ is g(0, k, 0, A, 0) and the returned value is M ^ k < 2 to support the edge case $$\k=1\$$.

g = (                        // g is a recursive function taking:
i,                         //   i = pointer in B[]
q,                         //   q = max. number of terms in the polynomial
d,                         //   d = degree
A,                         //   A[] = current vector, initialized to the
//         array of k 0's, returned by step 1
m,                         //   m = number of times B[i] has been used
h                          //   h = coefficient of the leading term
) =>                         //
i < n ?                    // if i is less than n:
c.map(c =>               //   for each coefficient c in c[]:
c * q &&               //     if both c and q are not 0
i >= r | !m &&         //     and B[i] can be repeated or m = 0,
g(                     //     do a recursive call:
i,                   //       leave i unchanged
q - 1,               //       decrement q
(D = m - ~i)         //       D is the degree of the new term
> d ? D : d,         //       update d to D if D > d
A.map((v, j) =>      //       update A[]:
v + B[i][j] * c),  //         add B[i][j] * c to each A[i]
m + n - r,           //       add the period to m
D > d ? c : h        //       update the coeff. of the leading term
),                     //     end of recursive call
g(                     //     do another recursive call with:
i + 1, q, d, A, 0, h //       i + 1, m = 0
)                      //       all other parameters unchanged
)                        //   end of map()
:                          // else (i = n):
M = h ^                  //   if the leading coeff. is not equal to 1
!A.some(x => x % k)  //   or some value in A[] is not 0 modulo k
| M < d ? M          //   or M is less than d, leave M unchanged
: d          //   else update it do d

format: plain


text:
# Math Help - Odd Integers

1. ## Odd Integers

What is the product if the largest of three consecutive odd integers whose sum is 129 is multiplied by 4?

Is the right equation:

x + (x + 2) + 4(x + 4) = 129?

2. no, first you need to find three consecutive odd integers whose sum is 129.

let the three
consecutive odd integers be $(x-2),x,(x+2)$,
so

$(x-2)+x+(x+2)=129$

solving this, you'll get $x$, and the largest odd integers is $(x+2)$

3. ## but...

Originally Posted by dedust
no, first you need to find three consecutive odd integers whose sum is 129.

let the three consecutive odd integers be $(x-2),x,(x+2)$,
so

$(x-2)+x+(x+2)=129$

solving this, you'll get $x$, and the largest odd integers is $(x+2)$
I've always seen x, x + 2 and x + 4 used to represent consecutive odd integers. Where did (x - 2) come from?

4. if you have $x$ as the first number, then the second is $x+2$ but now if you have $x$ as the second number then $x-2$ is the first,..is it clear??

just the trick to solve the problem

5. You can use whatever expressions provided that they are odd consecutives relative to $x$. You could have :

$(x + 88)$ and $(x + 90)$ and $(x + 92)$

or

$(x - 192)$ and $(x - 190)$ and $(x - 188)$

6. Originally Posted by Bacterius
You can use whatever expressions provided that they are odd consecutives relative to $x$. You could have :

$(x + 88)$ and $(x + 90)$ and $(x + 92)$

or

$(x - 192)$ and $(x - 190)$ and $(x - 188)$
yes,..choose the number that make it easier to solve

7. ## Ok...

Originally Posted by dedust
if you have $x$ as the first number, then the second is $x+2$ but now if you have $x$ as the second number then $x-2$ is the first,..is it clear??

just the trick to solve the problem
I thank you for this great trick and short cut. When I tried using my original equation, I ended up with 111/6, which didn't make sense to me at all.

8. ## Ray...

Originally Posted by Bacterius
You can use whatever expressions provided that they are odd consecutives relative to $x$. You could have :

$(x + 88)$ and $(x + 90)$ and $(x + 92)$

or

$(x - 192)$ and $(x - 190)$ and $(x - 188)$
Can we also use x, x + 2 and x + 4 as the list of consecutive odd integers to solve this question? When I did the algebra, I ended up with x = 111/6, which did not make sense to me at all.

9. Sure you can, but you got to rearrange your solution according to this at the end of your operations

10. ## Ray...

Originally Posted by Bacterius
Sure you can, but you got to rearrange your solution according to this at the end of your operations
Can you demonstrate for me?

11. Think about the meaning of $x$, and you should find out where something goes wrong

12. Originally Posted by sologuitar
Can we also use x, x + 2 and x + 4 as the list of consecutive odd integers to solve this question? When I did the algebra, I ended up with x = 111/6, which did not make sense to me at all.

how do you get x = 111/6 ?

Spoiler:
$x + (x+2) + (x+4) = 129$
$3x + 6 = 129$
$3x=123$
$x=41$

13. ## I see...

Originally Posted by dedust
how do you get x = 111/6 ?

Spoiler:
$x + (x+2) + (x+4) = 129$
$3x + 6 = 129$
$3x=123$
$x=41$
I made simple algebra errors that led to the wrong answer for x. Thanks for showing me the right way to find x.


text:
# Tag Info

15

If the wave is truly monochromatic then it will be sinusoidal. If it has a different profile then Fourier's theorem tells us that it can be built from an infinite series of (co)sine waves with increasing integer harmonics of the principle frequency (i.e. not monochromatic).

5

A plane wave is a single frequency , a sinusoidal variation in space and time by mathematical construction. Mathematically : the traveling wave solution to the wave equation ... is valid for any values of the wave parameters, and since any superposition of solutions is also a solution, then one can construct a wave packet solution as a sum of ...

5

The electromagnetic field in absence of charges and current is described by a wave equation. The solutions of the wave equations in a general setting (without symmetry contestants and without boundary conditions) are plane waves with a fixed frequency and momentum. These are purely sinusoidal $\propto \sin(k x-\omega t)$. Similarly, sound waves are the ...

3

The trick with invisibility is to arrange the flow of light so that when someone looks towards you they see whatever is behind you. This can be achieved by two methods: either a chameleon-like rapid colouring and patterning of your clothing to make it look like the scenery behind---with a 3d hologram-like effect for the best results. a powerful lens-like ...

3

The intuition that a black hole must have a very large mass is not true. The relevant parameter is how much mass is there within a (volume of some characteristic) radius. In the case of simple spherical objects, if a mass $M$ is concentrated within a radius $2GM/c^2$ then light (or anything else for that matter) cannot escape from the region $r< 2GM/c^2$, ...

2

If monochromatic light shines into our eyes, will that activate multiple types of cones or only one type of cone? Let's take for example monochromatic light with wavelength 520 nm (i.e. a yellow wavelength). Then your diagram (with the spectral sensitivity of the 3 types of cones) answers this question easily. L-type cones respond with strength 0.68 M-...

2

Rule One: Have Fun. Now, on to the optics. The refractive index is a bulk property of the material which means you cannot affect it with tiny amounts of things like food colorants. You can affect it with bulk constituents, like by adding sugar to water; in fact there is a handy little gizmo called a refractometer which is used by winemakers to tell how ...

1

I'd like to challenge your idea that the fact that a mix of red and blue gives something resembling violet implies that violet must be between red and blue. In practice, what you get from such mixture is a shade of purple. See the figure below. Here the black dashed line from blue to red covers the colors you can get by changing the amount of red and blue ...

1

Color is a double valued concept, different in physics and in perception. In Physics there is a one to one correspondence between color seen in the visible spectrum and the frequency of light. Electromagnetic spectrum with visible light highlighted The whole electromagnetic spectrum covers many frequencies above an below the visible, which are the ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
# Fluid Mechanics and Acoustics Laboratory - UMR 5509

LMFA - UMR 5509
Laboratoire de Mécanique des Fluides et d’Acoustique
Lyon
France

## Study of crystal growth situations

Séverine Millet, Valéry Botton, Daniel Henry, Hamda Ben Hadid, S. Kaddeche, F. Mokhtari, M. Albaric, D. Pelletier, J.P. Garandet, Y. Fautrelle, K. Zaidat

The solidification situations we study are known as vertical Bridgman (solidification from the bottom, it is the case of Silicon growth at INES) or horizontal Bridgman (solidification from the side, it is the case of metallic alloys solidification in the Afrodite experiment at SIMAP/EPM). These studies have also been developed in the frame of the PHC Maghreb program "Modeling and optimization of the purification of Silicon by directional solidification", which associates our research team with three teams from Algeria, Morocco and Tunisia.
In the case of Silicon growth, the objective is to get a good stirring of the melt for a better uniformity of its composition. Two approaches were studied: a stirring with an impeller or a non-intrusive stirring by acoustic streaming. The stirring by impeller has been studied experimentally (water setup and real melts) and numerically by M. Chatelain during his PhD (CEA funding), in collaboration between INES and our team [B25, A126, B26]. The thematic related with the stirring by acoustic streaming is presented in the rubric "Flows generated by ultrasound waves".
In a more applied direction and in connection with INES, we want to be able to estimate the effect of these flows on the impurities segregation. According to the models developed at INES by J.P. Garandet, these solutal effects, such as the segregation, can be estimated from the shear at the interface. In the frame of the PhD of N. El Ghani, we have developed an electrochemical method allowing the measurement of the shear at a wall in water and were thus able to characterize the solutal boundary layer induced by an acoustic streaming flow impinging a wall. In the frame of the PHC Maghreb program, we have also studied the effect that could be obtained by vibration, effect on the convection in the melt as well as on the impurities segregation (PhD of S. Bouarab).

Variation of the maximal velocity in a convective flow in a differentially heated cavity submitted to vibrations when the vibration angle $\alpha$ is changed (horizontal vibrations for $\alpha=0^\circ$ and vertical vibrations for $\alpha=90^\circ$). The pure convective flow turns in the trigonometric direction, but the vibrations ($90^\circ<\alpha<180^\circ$) can invert this flow.

In the case of metallic alloys solidification in the Afrodite experiment, the ingots are transversally confined and a temperature difference is applied between the endwalls in order to promote convection and the stirring of the compounds in the melt during the solidification. On this problem, the PhD of R. Boussaa on the three-dimensional numerical simulation of solidification allowed us to find the freckles observed experimentally, which are sources of brittleness in the solidified ingots [A120]. A two-dimensional model with a Hele-Shaw approach (2D½ model) has also been developed [A106]. The PhD of I. Hamzaoui allowed us to show that this 2D½ model was able to catch both purely convective situations and solidification configurations [A130].

Flow in the melt and position of the interface at the equilibrium state of solidification for right and left endwalls temperatures below and above the solidification temperature, respectively [A130].

Older work: crystal growth situations.

We studied more realistic crystal growth configurations taking into account a moving solid-liquid interface in the case of the Bridgman configuration. We particularly analyzed the convective flows in the liquid phase and the dopant concentration in the melt and in the crystal (macrosegregation phenomena) (PhD of S. Kaddeche). We later took into account periodic growth conditions and then considered pure solutal convection (PhD of F.Z. Haddad). These numerical studies were performed in collaboration with the Centre d’Etudes Nucléaires de Grenoble. They provided interesting results for the crystal growth community which were published in the Journal of Crystal Growth [A25, A27, A30, A46, A53, A54]. Within the frame of international collaborations, we also considered other crystal growth configurations (Czochralski, zone-melting) for which we particularly analyzed the flow transitions [A57, A78, A69].

Striations in the crystal due to a fluctuating interface velocity during horizontal Bridgman crystal growth [A46].


text:
Your browser doesn't appear to support the <canvas> element.
 flockaroo 2018-03-12cool, i already wanted to do some tutorials for people to get warm with it... :-) but for "default:" i would even suggest to set vertCoord to vec4(0) because otherwise on some systems a lot of unintialized vertices could be spawned which could result in a lot of random drawing action and stall the system.


text:
# Problem Set 1

Problem Set 1 [PDF] is now posted, and is due at the beginning of class (2:00pm) on Tuesday, 2 February. The LaTeX template for PS1 is here: ps1-template.tex. [Note: Problem 4 has been removed from PS1, see comment below for details.]

### 11 comments to Problem Set 1

• Renardy

In Sipser, a graph G is a subgraph of a graph H if:
1.) The nodes of G are a subset of the nodes of H
2.) The edges of G are the edges of H on the corresponding nodes

Unless I’m misreading something, this means that ALL of the edges in H that connect nodes in G must be present in G. This idea is also mimicked in the example (Figure 0.14). In other references, I’ve seen condition 2 to be more relaxed, in that the subgraph can have any SUBSET of the edges of H on the corresponding nodes.

Does this mean that, according to Sipser, a subgraph is entirely determined by the choice of nodes from the original graph?

• Yes, that is correct. The way Sipser defines the subgraph, the subgraph is completed determined by the subset of nodes. All edges involving just nodes in the subgraph are included in the subgraph. You’re right that there could be other ways to define subgraph that could make sense, but the way it is defined as a subset of nodes and all edges among those nodes is the standard way it is defined.

• Navid Hosseini pointed out that Problem 4 is seriously broken! The text of the question suggests that the alternative rule to “Rock crushes Scissors” is “Scissors is dulled by Rock”. In both cases, the implied beats relation is “Rock beats Scissors”. This makes the question stupid since the beats relation is obviously the same as the one Sipser defined.

I misread the RPS Society’s question as implying instead that “Scissors beats Rock”, which would make this a more interesting question.

So, Problem 4 is removed from PS1. If you want to try and answer the question I meant to ask, you are welcome to do so, but there is no credit for Problem 4, which now seems like an even sillier question than what it was intended to be!

Sorry for the confusion if you’ve been confused by this question.

• slam

Using LaTeX, what is the best/easiest way to draw DFA’s for the homework problem set, for example problem 8?

• The easiest way is to just hand-draw the DFA on the paper after you print it out with the other answers. This is fine, but has the drawback that you don’t have the DFA electronically.

Another approach is to draw it using some other drawing program like xfig, Visio, or PowerPoint, and generate a png image using that program. Then, you can include the image in your .tex document using the graphics package. Add this line to the preamble of the .tex file (where the other \usepackage commands are):

\usepackage{graphics}

Then, where you want the image to appear use:

\begin{center}
\includegraphics{imagefile.png}
\end{center}

You can add an optional scaling parameter if the image size is too big, e.g.,

\includegraphics[0.3]{imagefile.png}

If you’re a real LaTeX hacker, you can use LaTeX commands to draw the DFA directly. The VauCanSon-G package (http://www-igm.univ-mlv.fr/~lombardy/Vaucanson-G/) defines some LaTeX commands for drawing DFAs. I don’t recommend using this though, its more trouble than its worth for this.

• aml9j

These are all small details of the problems and it’s entirely possible I’m reading too much into things but…

for all of problem 8, I stated that l is an element of letters and d is an element of digits. Is this okay to use for my DFA instead of writing out the values?

Also, for problem 8d, should we assume that once we see ‘/*’ it is a comment? Or should we go further and wait until we see ‘/* some combination of numbers and letters */’ with the closing ‘*/’?

• > for all of problem 8, I stated that l is an element of letters and d is an element of digits.
> Is this okay to use for my DFA instead of writing out the values?

(I think you mean problem 9 as numbered originally, even though problem 4 is dropped.)

Yes, it is fine to use notations you introduce to represent sets of symbols in your DFA.

> Also, for problem 8d, should we assume that once we see ‘/*’ it is a comment?
> Or should we go further and wait until we see ‘/* some combination of numbers and letters */’ with the closing ‘*/’?

The way a traditional comment is defined, /* marks the start of the comment, and the first */ after it ends the comment. Your DFA should accept exactly the language of strings that do not contain either type of comment. For example,

“this is /* not a valid comment”

is in the language since the open comment is never closed in this string.

• mmk2d

Regarding Problem 3b:

On page 11 of Sipser a subgraph is defined as: “We say that a graph G is a subgraph of H if the nodes of G are a subset of the nodes of H…”

I was wondering if G contained no nodes, could it still be a subgraph of H? In other words, can a subgraph have zero nodes in general? Since the empty set is a subset of all sets, I was wondering if an empty graph would also be a subgraph of all graphs.

• I think you’ve already answered your own question! The empty set is indeed a subset of all sets, and there’s nothing in the definition of a graph that says it has to have at least one node.

• Nathan

Regarding Problem 8:

Does a DFA have to have an exit path for every element of the language. For example is the elements in the language are a,b can a state have an arrow leading away or looping back for a but no arrow for b. If so would the machine simply exit if it came to this state and read in a b from the input string.

• The transition (delta) function for a DFA should be completely defined. That means the transition function provides a mapping from every input pair to an output state. When we draw DFAs, though, it is not necessary to draw the full transition function. When there is no arrow from a given state on a particular symbol, that means the DFA is stuck if it sees that symbol in that state. In the transition function, this would be a transition to a permanent rejecting state (that is, a non-accepting state with an arrow back to itself on every input symbol). To keep the DFA diagrams more readable, though, we often do not draw the permanent rejecting state or the transitions to it, but instead assume if there is no transition for a symbol that the input is rejected.

For the PS, it is better to be explicit and show the full transition function (putting in the permanent reject state), since this way you know your DFA is completely defined. But, it is acceptable for full credit to leave them out since this is done by convention and in many of the diagrams in the Sipser book.


text:
Question

# If the 7th term of a harmonic progression is 8 and the 8th term is 7, than its 15th term is:-A). 16.B). 14.C). ${27}/{14}\;$.D). ${56}/{15}\;$.

Hint: The general term of the HP is given by $\dfrac{1}{a+\left( n-1 \right)d}$ where a is reciprocal of first term of HP and d is common difference in reciprocal of each term are this to get the result.

Now the 7th term of HP is equal to 8.
As described in the hint the general term is given by $\dfrac{1}{a+\left( n-1 \right)d}\ =\ {{T}_{n}}$
Now for the beneath term $n=7$
$\therefore \ {{T}_{7}}=\dfrac{1}{a+6d}$
$\because \ {{T}_{7}}=\ 8$
$\Rightarrow \ \dfrac{1}{a+6d}\ =\ 8$
$\Rightarrow \ a+6d=\ \dfrac{1}{8}$ (1)
Now the 8th term of HP is equal to 7.
$\therefore \,{{T}_{8}}\ =\ 7\ =\dfrac{1}{a+\left( 8-7 \right)d}$
$7\ =\ \dfrac{1}{a+7d}$
$\therefore \ a+7d\ =\ \dfrac{1}{7}$ (2)
Now on subtracting $eq\ \left( 1 \right)\ \text{from}\ \text{eq}\ \left( 2 \right)$
$\left( a+7d \right)-\left( a+6d \right)\ =\ \dfrac{1}{7}-\dfrac{1}{8}$
$a+7d-a-6d=\dfrac{8-7}{56}$
$\therefore \ d\ =\ \dfrac{1}{56}$
Now since we know the value of d, we can compute the value of a by substituting in equation (1), we get
$a\ +\ 6\ \times \ \dfrac{1}{56}=\ \dfrac{1}{8}$
$a\ =\ \dfrac{1}{8}-\dfrac{6}{56}$
$a\ =\ \dfrac{7-6}{56}$
$a\ =\ \dfrac{1}{56}$
Now if we want to compute the 15th term we can substitute the value of $a,d\ and\ n=15$ in general terms.
$\therefore \ {{T}_{15\ }}\ =\ \dfrac{1}{\dfrac{1}{56}+\left( 15-1 \right)\times \dfrac{1}{56}}$
$\Rightarrow \ \ \ {{T}_{15}}=\ \ \dfrac{1}{\dfrac{1}{56}+\dfrac{14}{56}}$
\Rightarrow \ \ \ {{T}_{15}}\ \ \ \ =\dfrac{1}{\begin{align} & 15 \\ & \overline{56} \\ \end{align}}
$\therefore \ {{T}_{15}}\ \ \ =\ \ \dfrac{56}{15}$
$\therefore$ The 15th term of HP is $\dfrac{56}{15}$

The correct option is D.

Note: If you can notice the general term in HP is reciprocal of general term of AP (arithmetic progression).
Therefore series of terms are a HP series when their reciprocal are in AP.


text:
Casimir operator

Could somebody please remind me why the e-values of the Casimir operator p.p (4-vector product) are the mass^2. This relation is clear to me when the field in question fulfils the Klein-Gordon equation but what about the general case?

I'm not too sure this will satisfy you, but this is basically Einstein's $$E^2-\vec{p}^{.2}=m^2$$ (so Klein-Gordon is the general case indeed). For a spin-1/2 field, it si clear that if it satisfies Dirac then it satisfies KG...

Thanks for the reply, but what you are pointing out is exactly my concern: The relativistic E^2=p.p+m^2 only comes from the field satisfying Klein Gordon which is the case when we have a scalar field or a spinor field but for an arbitrary theory I do not see why the e-values associated with the Casimir operator p.p (4-vectors) should be the mass^2.

strangerep
Th[...] is exactly my concern: The relativistic E^2=p.p+m^2 only comes from the field satisfying Klein Gordon which is the case when we have a scalar field or a spinor field but for an arbitrary theory I do not see why the e-values associated with the Casimir operator p.p (4-vectors) should be the mass^2.

The short answer is that relativistic quantum fields correspond to
irreducible representations of the Poincare group (else they are not
relativistically covariant). A "representation" of a group just means
that we have some vector space or other (1-dimensional, 2-dimensional,.....,
or even infinite-dimensional) and the group elements can be represented as
matrix operators in that vector space. One says that the space "carries" a
representation of the group. A representation is called irreducible if there
are no non-trivial invariant subgroups, i.e: if any two subspaces of the vector
will mix together, for some group element(s).

One classifies all irreducible representations of a given (abstract) group
by the eigenvalues of the group's Casimir operators (which commute
with all other group operators) and one other operator. For the Poincare
group the Casimirs are mass^2 (i.e: P^2), W^2 (square of Pauli-Lubansky
operator - the covariant version of total spin). The 3rd operator is usually
taken to be a spin component orthogonal to the 4-momentum.

Back in 1939, Wigner found that we can classify all irreducible
representations of the Poincare group in this way, and that the eigenvalues
of the total spin operator (W^2) are 0,1/2,1,..... The spin-1/2 fields can be
represented in a space of 2 complex dimensions - this corresponds to a
neutrino field. One can also complex-conjugate this space and get an
inequivalent representation of spin-1/2 (corresponding to anti-neutrinos).
The direct sum of these two spaces corresponds to the (massive) Dirac
field.

So to answer your question: for a massive spin-1/2 field, the Poincare
group is represented on the direct sum of the two 2-complex-dimensional
spaces mentioned above. The Casimir operator P^2, represented in
that same space, still corresponds to a mass^2 operator when acting
on elements of that vector space, by construction.

And... I think I should stop here until I see whether what I've written
above is making any sense.

Meir Achuz
Homework Helper
Gold Member
Thanks for the reply, but what you are pointing out is exactly my concern: The relativistic E^2=p.p+m^2 only comes from the field satisfying Klein Gordon which is the case when we have a scalar field or a spinor field but for an arbitrary theory I do not see why the e-values associated with the Casimir operator p.p (4-vectors) should be the mass^2.
Most physicists define the mass of an object as the invariant length of its four-momentum. This turns out to be a useful definition. It has nothing to do with a wave equation.

I agree with the earlier posts and should rephrase my question: Is the coefficient of the quadratic term of a fundamental field in an arbitrary Lagrangian density always related to the eigenvalue of the Casimir operator p.p (4-momentum squared)? If this is the case, could you pleae tell me how and why it should be related? Thanks in advance

i can think of something though im not sure whether it'll satisfy you. you see a quadratic in the fundamental fields is lorentz invariant and so are the eigenvalues of a casimir.it seems to be necessary, even if not sufficient

dextercioby
Homework Helper
I agree with the earlier posts and should rephrase my question: Is the coefficient of the quadratic term of a fundamental field in an arbitrary Lagrangian density always related to the eigenvalue of the Casimir operator p.p (4-momentum squared)? If this is the case, could you pleae tell me how and why it should be related? Thanks in advance

Yes, it is. What is the purpose of builing a lagrangian for an arbitrary classical field ? To use it in the quantization formalism. Therefore, we need a mass term, since the mass of the quanta of the field is essential in the quantization...

dextercioby
Homework Helper
Could somebody please remind me why the e-values of the Casimir operator p.p (4-vector product) are the mass^2.

That's how we define the mass of the quanta of the field.

strangerep
[...] rephrase my question: Is the coefficient of the quadratic term of a fundamental field in an arbitrary Lagrangian density always related to the eigenvalue of the Casimir operator p.p (4-momentum squared)? If this is the case, could you pleae tell me how and why it should be related?

A (relativistic) Lagrangian represents a particular physical theory
constructed within the representation carrier space we call "Minkowski" space.
In Minkowski space, the translation generators are represented by simple
differential operators, acting on functions of the Minkowski space coordinates.
Such functions are spanned by a plane wave basis.

Therefore, a representation of P^2 in this carrier space is a quadratic
derivative term.

"Therefore, we need a mass term, since the mass of the quanta of the field is essential in the quantization..."

sorry but thats not always essential right? for gauge fields you dont write a mass term and its as impotant as any...

Last edited:
dextercioby
Homework Helper
yes, it's true. For classical fields, a mass term destroys gauge invariance.

I am trying to understand Casimirs. The Definition I was given was:

A Casimir operator is an operator which commutes with all group actions
on any representation.

The language is based on "group actions" which is still a little vague. As Definitions go is this sufficiently equivalent to the operator commuting with all the infinitesimal generators of the Group Algebra?

For example: If I take an Algebra $$\mbox{so(3)}$$, identify its infinitesimal generators, $$\left{ \tau^i \right}$$ and take an operator, call it, $$L^2$$ and find that

$$\left[ L^2, \tau^i \right]=0$$

for each $$i=1,2,3$$.

Then this is sufficient to claim $$L^2$$ is a Casimir of $$\mbox{SO(3)}$$?

samalkhaiat
the operator commuting with all the infinitesimal generators of the Group Algebra?

This is the one.

For example: If I take an Algebra $$\mbox{so(3)}$$, identify its infinitesimal generators, $$\left{ \tau^i \right}$$ and take an operator, call it, $$L^2$$ and find that

$$\left[ L^2, \tau^i \right]=0$$

for each $$i=1,2,3$$.

Then this is sufficient to claim $$L^2$$ is a Casimir of $$\mbox{SO(3)}$$?

Provided that

1) $L^{2}$ is invariant under SO(3) transformations.
2) it is constructed out of the group generators.

regards

sam

Thank you Sam.


text:
# Finding Shortest Path in the Plane with Obstacles

[CG]Maxime
16.2K views

Among the games I have developed on CodinGame, one of my favorites is Ghost in the Cell because it gave me the opportunity to solve a very interesting problem: finding the shortest path in a plane while avoiding obstacles. This is an algorithm I've been taught during a robot motion planning class when I was a student but I never had the opportunity to implement it.

In this article, I will show you how to compute a path from one factory to another while avoiding other factories. A factory is simply a round obstacle.

The algorithm will be divided in 3 steps:

## Computation of the Polygons

The obstacles are round, however we need a discrete amount of vertices to build the visibility graph. A circle can easily be approximated by a regular polygon.

First, some vocabulary:

• A regular polygon is a polygon equiangular and equilateral
• The apothem ($a$) is the distance from the center to the midpoint of one of its sides
• The circumradius ($R$) is the distance from the center to one of its vertices
• The inscribed circle of a regular polygon is a circle with the same center and radius $a$

We are looking for a polygon for which the inscribed circle is the radius of a factory, plus a gap to forbid a path to go too close to an obstacle (too dangerous). The apothem of the polygon is : $a = obstacle.radius + extraSpace$. The circumradius can be calculated from the apothem and the number of edges: $R = \frac{a}{cos(\pi / n)}$.

The coordinates of the vertices of a polygon of $n$ edges are:

$\left \\left\{ \begin\left\{matrix\right\} x = obstacle.x + R \cdot cos\left(t\right) \\ y = obstacle.y + R \cdot sin\left(t\right) \end\left\{matrix\right\} \right .\quad\text\left\{with\right\}\quad t \in \left[0, \frac\left\{2\pi\right\}\left\{n\right\}, 2\frac\left\{2\pi\right\}\left\{n\right\}, 3\frac\left\{2\pi\right\}\left\{n\right\}, ..., \left(n - 1\right)\frac\left\{2\pi\right\}\left\{n\right\}\right]$

Here's the implementation of the polygon function:

Feel free to play with the number of edges.

## Visibility Graph

From the set of vertices of all the polygons, we create a graph called Visibility Graph. Each vertex is connected to all the vertices that can be reached by a direct line without crossing any obstacle.

For this, we need a function to detect an intersection between two segments. We'll also use a function to detect an intersection with a circle but it was not strictly necessary (this simplifies the code). The function directPath returns true when two points can be connected without intersecting a polygon.

The function buildGraph iterates over all the vertices of all the polygons and create a bidirectional edge when directPath returns true. We also add a unidirectional edge from each center (these edges only allows to exit a factory).

## Shortest Path

Any conventional shortest path algorithm can be used to compute the path from a factory to another using the visibility graph. Here's the implementation of an A*. For the sake of simplicity, I've used a sorted array instead of a priority queue, feel free to improve that part.

By increasing the number of edges for each polygon, the path become smoother.


text:
# Lesson 9: Formula for the Area of a Triangle

Let’s write and use a formula to find the area of a triangle.

## 9.1: Bases and Heights of a Triangle

Study the examples and non-examples of bases and heights in a triangle. Answer the questions that follow.

• These dashed segments represent heights of the triangle.
• These dashed segments do not represent heights of the triangle.

Select all the statements that are true about bases and heights in a triangle.

1. Any side of a triangle can be a base.
2. There is only one possible height.
3. A height is always one of the sides of a triangle.
4. A height that corresponds to a base must be drawn at an acute angle to the base.
1. A height that corresponds to a base must be drawn at a right angle to the base.
2. Once we choose a base, there is only one segment that represents the corresponding height.
3. A segment representing a height must go through a vertex.

## 9.2: Finding the Formula for Area of a Triangle

• For each triangle, label a side that can be used as the base and a segment showing its corresponding height.
• Record the measurements for the base and height in the table, and find the area of the triangle. (The side length of each square on the grid is 1 unit.)
• In the last row, write an expression for the area of any triangle using $b$ and $h$.
row 0 triangle base (units) height (units) area (square units)
row 1  A
row 2 B
row 3 C
row 4 D
row 5 any triangle $b$ $h$

## 9.3: Applying the Formula for Area of Triangles

For each triangle, circle a base measurement that you can use to find the area of the triangle. Then, find the area of any three triangles. Show your reasoning.

## Summary

• We can choose any of the three sides of a triangle to call the base. The term “base” refers to both the side and its length (the measurement).
• The corresponding height is the length of a perpendicular segment from the base to the vertex opposite of it. The opposite vertex is the vertex that is not an endpoint of the base.

Here are three pairs of bases and heights for the same triangle. The dashed segments in the diagrams represent heights.

A segment showing a height must be drawn at a right angle to the base, but it can be drawn in more than one place. It does not have to go through the opposite vertex, as long as it connects the base and a line that is parallel to the base and goes through the opposite vertex, as shown here.

The base-height pairs in a triangle are closely related to those in a parallelogram. Recall that two copies of a triangle can be composed into one or more parallelograms. Each parallelogram shares at least one base with the triangle.

For any base that they share, the corresponding height is also shared, as shown by the dashed segments.

We can use the base-height measurements and our knowledge of parallelograms to find the area of any triangle.

• The formula for the area of a parallelogram with base $b$ and height $h$ is $b \boldcdot h$.
• A triangle takes up half of the area of a parallelogram with the same base and height. We can therefore express the area $A$ of a triangle as: $$A = \frac12 \boldcdot b \boldcdot h$$
• The area of Triangle A is 15 square units because $\frac12 \boldcdot 5 \boldcdot 6=15$.

• The area of Triangle B is 4.5 square units because $\frac12 \boldcdot 3 \boldcdot 3 = 4.5$.

• The area of Triangle C is 24 square units because $\frac12 \boldcdot 12 \boldcdot 4 = 24$.

In each case, one side of the triangle is the base but neither of the other sides is the height. This is because the angle between them is not a right angle.

In right triangles, however, the two sides that are perpendicular can be a base and a height.

The area of this triangle is 18 square units whether we use 4 units or 9 units for the base.

## Glossary

opposite vertex

#### opposite vertex

When you choose a side to be the base in a triangle, the vertex that is not an endpoint of the base is the opposite vertex.

Point $A$ is the opposite vertex to the base $\overline{BC}$

base/height of a triangle

#### base/height of a triangle

Any of the three sides of a triangle can be chosen as a base. The term base can also refer to the length of this side. Once we have chosen a base, the corresponding height is the length of a perpendicular segment from the base to the vertex opposite it. The opposite vertex is the vertex that is not an endpoint of the base.