text:
# Nikola Tesla

1. Dec 27, 2008

### Rick_Schwartz

Hello to all! I have but 1 simple question: Has the secret of Nikola Tesla's ability to run a car on power from "the ethos" ever been revealed? Was it a permanent magnet motor the didn't need an external power source? I can see all the skeptics eyebrows being raised as we speak regarding "perpetual motion", but since he was not regarded as a charlatan or fraud, isn't that exactly what he did?? Thank you in advance for all replies!

Last edited by a moderator: Jun 19, 2009
2. Dec 27, 2008

### Staff: Mentor

Tesla was no fraud, but people have attached all kinds of crackpot nonsense to him because he is somewhat mysterious.

3. Jun 19, 2009

### AltScience

Compare "Ether" to "Quantum Vacuum" for some interesting similarities.

Tesla was using a theory of electro-magnetism that is different than the popular academic one that we are familiar with. Are we all familiar with the idea that Herzt left half the equations unsolved?

"All kinds of crackpot nonsense" from both sides of the debate come from a misunderstanding of how to use language. Is it possible that Kierkegaard's notion of "the acceptance of objective uncertainty" seems vital to a more open scientific research?

Last edited by a moderator: Jun 19, 2009
4. Jun 19, 2009

### Integral

Staff Emeritus
Could you provide a link to peer reviewed journel which backs up this claim? To the best of my knowledge Tesla did nothing that cannot be explained by Maxwells Equations.
So you believe that noone has done anything with Maxwells Equations since Hertz? Perhaps you need to take a Universtiy course in E&M.
The language most crackpots do not understand is Mathematics.

5. Jun 19, 2009

### RonL

Nikola Tesla, is my number one hero from history, I believe if he and Edison had been able to get along, and if he had worked with Charles E Tripler, for just a short time, there would be no fuel problems of any sort.
As for his electric car, I have seen no evidence of anything special that got buried in time.

As for him becoming a recluse, I think I understand his frustration at explaining far out thoughts that became misinterpeted by people that had not much imagination in the areas he loved.

If you look at the money that went through his hands for the times, only poor business management caused him to die in poverty.

Ron

6. Jun 19, 2009

### TurtleMeister

I read a biography on him many years ago and yes, he was a mysterious person. But that was what made him so interesting. Some of his ideas changed the world, and some of them seemed almost crackpot. I think there are a couple of his public demonstrations that have never been duplicated.

7. Jun 19, 2009

### RonL

OUCH!!!

8. Jun 20, 2009

### gary350

About 90% of the stuff writting about Tesla is made up non sense. I have no idea how all the worthless information every became available. If you become a member of the Tesla Coil forum those guys can stear you in the correct direction on information that is TRUE and it works. We have several 1000 members.

To become a TC member send an email to, tesla@pupman.com put the word subscribe in the subject line and the body. Only 1 word in each line that is all. You will be a memeber in about 24 hours.

Are you related to Glen Schwartz in Mt Carmel Illinois?

9. Jun 20, 2009

### HallsofIvy

Staff Emeritus
For a "number one hero" you don't seem to know much about him. He was never a "recluse" and he did not die in poverty! In 1917, 26 years before his death, he was awarded the "Edison medal" considered, at the time, the most prestigious award for electrical science- ironic considering the feud between him and Edison. Even more ironic, today it is the "Tesla medal" that is today considered most prestigious. He gave lavish dinner parties at the Hotel New Yorker where he lived for the last 20 years of his life.

As for his "ethos", he was essentially talking about electro-magnetic fields- arguing that energy can be transmitted through such fields. Well, it can- that's what radio is (and part of Marconi's work was based on his) but the problem is that "1/r2" drop off. When you transmit power, you waste a heck of a lot of it. Tesla did one demonstration in which he lit up electric lights at a distance of 25 miles, wirelessly, but he had to generate and enormous amount of power, most of which was wasted, being transmitted off where there were no recievers. Microwaves are a bit more "aimable" but, still, electrical engineering is known as "power engineering" and electronic engineering is known as "signal engineering".

10. Jun 21, 2009

### RonL

I might need to revisit the remark about him being a recluse, he did go out, but feeding pigeons became his biggest pastime in his last days. He did die impoverished at the age of 86.

I'll check the books I have, but it appears you might need a little quick read about his life as well.
Overall my statement stands, and only in the last 20 years, has his life works been brought to the attention of mainstream recognition.

Last edited: Jun 22, 2009
11. Jun 22, 2009

### GrizzlyBat

Is it true that he tried to make a tower that would give people wireless power? and if so, wouldn't it waste a lot of energy? Or am I thinking of something else?

12. Jun 22, 2009

### mgb_phys

Yes

He thought he could efficiently transmit power using a resonant frequency of the Earth. He was wrong - it looks like he made a few mistakes and his data for the existence of long range waves in the Earth was based on some faulty experiments with lightning.
He never actually demonstrated efficiently coupled power transmission.
You can (reasonably) efficiently transfer power inductively, but only on distances about equal to the size of the transmitter/receiver - which is great for electric toothbrushes but doesn't replace power lines.
There are a few experiments that have managed tuned systems that can go a bit further. Confusingly there is also a Tesla effect that is used in these systems, but wasn't used by Tesla.

13. Jun 22, 2009

### TurtleMeister

You're probably thinking of Wardenclyffe Tower. Just google Tesla Tower. And yes, it would waste a lot of energy. I think the main reason for the construction of Wardenclyffe Tower was for telecommunications, but wireless power transmission was Tesla's dream.

14. Jul 14, 2009

### 2kbucks

Having recently read his biography, I'm fairly certian he did in fact, die impoverished. He had a hotel bill unpaid at the time of his death as I remember. But he did also have millions of dollars run through his hands during his life. Tesla, while an absolute scientific genius and whom I believe to be the most influential person in history, had very little financial sense, coupled with poor comprehension of the greed of man. For example, he willingly signed over all his AC polyphase patents to Westinghouse for way less than what they were worth or had already earned for Nic, just by good ol George asking him to. I think the original deal was for something like $.05/hp of power created from the AC system. Which would have made Tesla the Richest man in the World in a decades time. George later told him that he could not pay what was owed and could not aquire new financial backing with that contract in effect. Westinghouse was himself in financial trouble at the time and so he asked Tesla if he would absolve the debt and sell him the patents out right for somewhere between$50k and \$100k(debated) with no per/hp clause. Tesla agreed in the hopes of gaining more funding from GW for future projects. One of his greatest dreams aside from becoming a US citizen was to become a millionare, which he never did due to savvy biz decisions like this one.....

Now I could be very ignorant to the actual physics but I believe that Tesla's Wardenclyffe tower and the car were meant to operate with "non-hertizean" or "standing" or "scalar" waves that did not have the same inverse square drop off. I'm not really sure what the differences are, it's just what I've read. Is this part verifiable by anyone? Sorry for not being able to back up my own thoughts, I'm pretty new to Physics.

15. Jul 15, 2009

### Born2bwire

One thing people need to keep in mind is that Tesla lived and researched during the infancy of electromagnetism. We have researching classical electromagnetics for around 130 years or so, but Tesla was working on them in the beginning. Maxwell developed the full equations in the 1870's or so. Hertz demonstrated the existence of electromagnetic waves via experiment in the 1880's. Marconni demonstrated the ability for long range electromagnetic communication in the 1900's.

So a lot of what Tesla was doing was at the forefront of a new field. So a lot of his ideas proved to be revolutionary but many of them would never work. It is not really his fault since he was one of the pioneers at the time. For some reason though, people seem to assign to him all sorts of absolute garbage when it comes to his research and abilities. Wireless power transmission? We know now that it is not a feasible means of transmission due to the long history of research into antennas. But we do use it to charge the batteries for low power devices using near field antennas, like medical implants. Death ray? Death rays were being researched by several people in the 30's and 40's (Japanese are one that spring to mind) because of the recently invented microwave generators. It quickly became apparent that they were not feasible although today we have a similar device with the Active Denial System. Free energy from the ethos? What the hell does that even mean? Back then, the ether model was still popular but we now know that it is not a correct model.

Seriously, the theory behind electromagnetics has been complete for over 130 years. It is silly to think that Tesla somehow had special insight into it that hasn't already been revisited since then.

16. Jul 15, 2009

### gary350

I have been on the Tesla Coil Forum for going on 9 years. This type of stuff comes up on the forum all the time when new folks bring it up all the time. Most of what you read about Tesla is non sense. News reporters were like the National Inquire they just made crap up. I don't keep up with what is true and false that is not my thing. I do know Tesla was flat broke and couldn't get anymore money from supporters that is why he sold to Westinghouse. Tesla never light up any light bulbs at a distance of 25 miles without wires. Marconni stole one of Tesla's ideas and developed it and got a patent before Tesla applied for the patent. Edison wanted to use DC to power cities and Tesla proved AC was better, Edison lost a big contract to Tesla and the fued began. Tesla never made a spark longer than 25 ft. Tesla was the MAD SCIENTIST of his time, anytime a rumor surfaced Tesla got credit for it.

Last edited: Jul 15, 2009
17. Jul 15, 2009

### AltScience

Gerry Vassilatos points out in Secrets of Cold War Technology that the Tesla Transformer is not an "electrical" device in the way commonly understood. Much of the criticism in this thread fails to recognize that Tesla was working with an impulse apparatus designed to use radiant shockwaves to produce pure voltage without current.

Both Sir Oliver Lodge and Nikola Tesla subscribed to an Ether Theory of Electrodynamics. While this is another can of worms...these are the worms needed to catch the elusive fish that Tesla and Lodge were gaming for. The model of the Quantum Vacuum as applied by Free Energy researchers like Tom Bearden is closer to the Ether Theory used by Tesla in his discoveries.

There are substantial differences from what is taught in modern university and the working model that Tesla and Lodge were using. It is this fact that should slow us down and open our minds to new possibilities.

18. Jul 15, 2009

### Staff: Mentor

Why? As has been pointed out several times, EM research has progressed far beyond Tesla's understanding in the 65 years since he died. Going backwards is not a way to go forwards.

19. Jul 15, 2009

### Born2bwire

In no way is ether theory like the quantum vacuum. The quantum vacuum is still a vacuum, devoid of real photons and matter. Ether was thought of a medium that propagated the electromagnetic wave and comes with all the consequences of a physical medium. Ideas like ether drag and such are examples of experimentally debunked properties of said ether. The fact that Tesla would work assuming an ether strongly suggests that he was still caught up in the thinking of very early electromagnetics. It should not be any surprise then that he would seriously research topics and ideas that would prove unfeasible and ridiculous by modern standards simply because we have the hindsight of many many years of research and experimentation. Carnot subscribed to the idea of calorics as being massless particles that mediated the transfer of heat. The idea is of course very wrong but he was still able to produce his ideal Carnot engine that is still a very fundamental building block of modern thermodynamic theory. You can find many ideas and theories from many of history's prominent scientists that are wrong by modern theory and experiments. Why should Tesla be any different?


text:
Found at least 20 result(s)

### 04.10.2018 (Thursday)

#### tba

Regular Seminar Diego Rodriguez-Gomez (Oviedo U.)

 at: 14:00 QMWroom G O Jones 610 abstract: tba

### 23.07.2018 (Monday)

#### Einstein Double Field Equations

Regular Seminar Jeong-Hyuck Park (Sogang University)

 at: 15:30 QMWroom 410 abstract: String theory predicts its own gravity rather than GR. In General Relativity the metric is the only geometric and gravitational field, whereas in string theory the closed-string massless sector comprises a skew-symmetric B-field and the string dilaton in addition to the metric. Furthermore, these three fields transform into each other under T-duality. This hints at a natural augmentation of GR: upon treating the whole closed string massless sector as stringy graviton fields, Double Field Theory may evolve into Stringy Gravity'. Equipped with an O(D,D) covariant differential geometry beyond Riemann, we spell out the definitions of the stringy Einstein curvature tensor and the stringy Energy-Momentum tensor. Equating them, all the equations of motion of the closed string massless sector are unified into a single expression which we dub the Einstein Double Field Equations.

### 13.03.2018 (Tuesday)

#### tba

Regular Seminar Attila Csikasz-Nagy (KCL)

 at: 15:00 City U.room B103 abstract:

### 27.02.2018 (Tuesday)

#### Topological strings and 6d SCFTs

Regular Seminar Amir-Kian Kashani-Poor (ENS)

 at: 15:00 City U.room B103 abstract: The topological string is a simplified version of physical string theory. It is of interest because it computes the BPS spectrum of relevant string theory compactifications, but also because it shares structural properties of physical string theory, Dualities and symmetries which often must be argued for arduously in the physical string can often be verified by computation in the topological setting. The central observable of the theory is the topological string partition function Z_top. This quantity has an eerie habit of making surprise appearances in many areas of mathematical physics. Numerous techniques exist for its computation in various expansions in parameters of the theory, yet to date, no satisfactory closed form for this quantity is known. In this talk, after reviewing notions of topological string theory with an emphasis on the interplay between worldsheet and target space physics (one of the structural similarities between the physical and the topological string alluded to above), I will report on progress in computing Z_top in settings where it is related to enigmatic 6d theories.

### 04.10.2017 (Wednesday)

#### The topologically twisted index on H2xS1 and its relation to the entropy of hyperbolic AdS4 black holes.

Regular Seminar Alejandro Cabo-Bizet (KCL)

 at: 13:15 KCLroom K4.31 abstract: I will start by sketching the computation of the topologically twisted index on H2xS1 and its evaluation in ABJM theory in the large N limit with k=1. Then after, I will review the key points behind the construction of magnetically charged (hyperbolic) AdS4 black holes on STU gauged SUGRA and will conclude by stating how the aformentioned index -- upon extremization -- coincides with the entropy of the latter black holes in the large N limit (with k=1).

### 05.07.2017 (Wednesday)

#### Holography of BCFT

Regular Seminar Chong-Sun Chu (NCTS, Hsinchu and Taiwan, Natl. Tsing Hua U.)

 at: 11:30 QMWroom 610 abstract: In this talk, I will discuss about the holography of boundary Conformal Field theory. I will show how boundary Weyl Anomaly can be obtained from holography. New universal relations between the shape dependence of Casimir effects and boundary Weyl anomaly will also be pointed out and discussed from the point of view of holography.

### 09.11.2016 (Wednesday)

#### An algebraic approach to the classification of supergravity backgrounds

Regular Seminar Jose Miguel Figueroa-O'Farrill (Edinburgh)

 at: 13:15 KCLroom G01 Norfolk Building abstract: I will report on joint work with Andrea Santi outlining an algebraic reformulation of the classification problem of eleven-dimensional supergravity backgrounds. The basic object of study is the Killing superalgebra of the background, whose algebraic structure has recently been elucidated. If time permits I will also comment on work also involving Paul de Medeiros applying these techniques to the construction of rigidly supersymmetric theories in curved spaces.

### 29.08.2016 (Monday)

#### STiL 2016: Supersymmetry, Geometry, and Holography

Exceptional Seminar - - (-)

 at: 10:00 KCLroom tba abstract: 29 August - 3 September, King's College London. This workshop intends to bring together leading experts and young researchers working on the broad themes of quantum field theory, black holes and gravitation, and holography, so as to share new ideas, calculations, and results in a focused setting. The topics covered in the workshop include: Symmetries and dualities in field theory and gravity Classical and quantum aspects of black holes Supersymmetric localization and exact results Mathematical aspects of string theory Supergravity solutions and holography Website Registration will be closed on 8 July 2016 or when positions are filled.

### 17.02.2016 (Wednesday)

#### Brane Brick Models, Toric Calabi-Yau 4-folds and 2d (0,2) Quivers

Exceptional Seminar Rak-Kyeong Seong (KIAS)

 at: 15:30 KCLroom K6.63 abstract: In this talk, I will discuss Type IIA brane configurations consisting of D4-branes suspended between NS5-branes which represent a large class of 2d (0,2) quiver gauge theories. We call these new constructions Brane Brick models. These are T-dual to D1-branes over singular toric Calabi-Yau 4-folds and encode information about the probed Calabi-Yau geometry as well as the corresponding GLSM. If time permits, I will present how Brane Brick models naturally realise in terms of a brane configuration 2d (0,2) Gadde-Gukov-Putrov triality.

### 16.02.2016 (Tuesday)

#### Yang-Mills Theory and the ABC Conjecture

Regular Seminar Yang-Hui He (City)

 at: 15:00 City U.room B103 abstract: We establish a precise correspondence between the ABC Conjecture and N=4 super-Yang-Mills theory. This is achieved by combining three ingredients: (i) Elkies' method of mapping ABC-triples to elliptic curves in his demonstration that ABC implies Mordell/Faltings; (ii) an explicit pair of elliptic curve and associated Belyi map given by Khadjavi-Scharaschkin; and (iii) the fact that the bipartite brane-tiling/dimer model for a gauge theory with toric moduli space is a particular dessin d'enfant in the sense of Grothendieck. We explore this correspondence for the highest quality ABC-triples as well as large samples of random triples. The Conjecture itself is mapped to a statement about the fundamental domain of the toroidal compactification of the string realization of N=4 SYM.

### 26.11.2015 (Thursday)

Regular Seminar Yang-Hui He (City)

 at: 14:00 QMWroom G.O. Jones 610 abstract: We study the web of correspondences linking the exceptional Lie algebras E8,7,6 and the sporadic simple groups Monster, Baby and the largest Fischer group. We will survey some old observations from the perspective of Moonshine and representation theory and present some new ones from that of congruence groups and enumerative geometry. Based on joint work with John McKay.

### 19.11.2015 (Thursday)

#### 5d theories on curved backgrounds, Yang-Mills deformations and instantons

Regular Seminar Diego Rodriguez-Gomez (Universidad de Oviedo)

 at: 14:00 QMWroom G.O. Jones 610 abstract: 5d theories can be at fixed points, in many cases exhibiting rather amusing properties. In this talk we will study several properties of these fixed point theories. In particular, we will describe how to put them supersymmetrically in curved spaces. As a consequence, we will discuss when a deformation to a Yang-Mills theory is possible. The latter typically exhibit a smaller global symmetry that that of the fixed point theory, which, from the YM point of view, appears as an enhanced symmetry. In this enhancement instantons play a pivotal role, and we will discuss several aspects of these.

### 18.11.2015 (Wednesday)

#### Polygon Seminar: An introduction to the Hilbert series as operator counting

Triangular Seminar Diego Rodriguez-Gomez (University of Oviedo)

 at: 15:00 QMWroom GO Jones 610 abstract: Counting operators in supersymmetric field theories is very interesting, as the corresponding generating functions encode properties of the field theory. In this lecture we will mostly concentrate on 4d SUSY field theories. After reviewing some basic notions about SUSY field theories leading to the notion of chiral ring, we will introduce a generating function enumerating operators in the ring. This function is the so-called Hilbert series. In the case of SCFTs with a gravity dual, we will show how this function recovers geometric properties of the dual gravity background. The uses of the Hilbert series go beyond this, since, as we will see, being a counting of operators, it is of relevance in the computation of instanton partition functions for pure gauge theories. In the second part of the lecture we will briefly touch upon these issues.

### 08.10.2015 (Thursday)

#### All gaugings and stable de Sitter in D=7 half-maximal supergravity

Regular Seminar Jose Fernandez-Melgarejo (Harvard)

 at: 13:30 ICroom H503 abstract: We study the general formulation of gauged supergravity in seven dimensions with sixteen supercharges keeping duality covariance by means of the embedding tensor formalism. We first classify all inequivalent duality orbits of consistent deformations. Secondly, we analyse the complete set of critical points in a systematic way. Interestingly, we find the first examples of stable de Sitter solutions within a theory with such a large amount of supersymmetry.

### 30.04.2015 (Thursday)

#### Hidden symmetries of scattering amplitudes (and of Hydrogen atom)

Regular Seminar Simon Caron-Huot (NBI)

 at: 14:00 QMWroom G.O. Jones 610 abstract: Physical systems with unexpected, or hidden,’ symmetries have often played an important role in physics, beginning with the classical Kepler problem whose Laplace-Runge-Lenz vector ensures the closure of planetary orbits, and degeneracies of the Hydrogen spectrum. I will describe how precisely the same symmetry governs a unique four-dimensional quantum field theory, a maximally supersymmetric (`N=4') cousin of the strong-interaction Yang-Mills theory. After reviewing progress in recent years in using these symmetries to solve this model, I will describe novel applications involving massive particles. Combining the Laplace-Runge-Lenz vector with relativity then yields a novel way to calculate the spectrum of its Hydrogen-like bound states, including relativistic corrections. Based on 1408.0296.

### 10.12.2014 (Wednesday)

#### Eta Products, BPS States and K3 Surfaces

Regular Seminar Yang-Hui He (City University)

 at: 13:15 KCLroom G.01 abstract: Inspired by the multiplicative nature of the Ramanujan modular discriminant, Delta, we consider physical realizations of certain multiplicative products over the Dedekind eta-function in two parallel directions: the generating function of BPS states in certain heterotic orbifolds and elliptic K3 surfaces associated to congruence subgroups of the modular group. We show that they are, after string duality to type II, the same K3 surfaces admitting Nikulin automorphisms. In due course, we will present some identities arising from q-expansions as well as relations to the sporadic Mathieu group M24.

### 03.12.2014 (Wednesday)

#### Polygon Seminar: Gauge Theories and Calabi-Yau Manifolds

Triangular Seminar Yang-Hui He (City University)

 at: 15:30 QMWroom Francis Bancroft 1.15 abstract:

### 05.11.2014 (Wednesday)

#### Gerbes on the Lattice

Regular Seminar Ron Reid-Edwards (Hull)

 at: 14:00 ICroom H503 abstract: Abelian gerbes play a ubiquitous role in string and supergravity theories. It is conjectured that non-abelian gerbe theories exist, but a satisfactory explicit construction of such a theory has not yet been achieved. Inspired by the possibility that a non-abelian theory of gerbes may be possible on non-conventional spacetimes, I will consider a toy model on a lattice that allows one to make some progress in this problem. In this talk, I will show how abelian gerbe theories may be described naturally on the lattice. I will outline a non-abelian generalisation and show how, under dimensional reduction, such theories give rise to lattice Yang-Mills.

### 21.03.2014 (Friday)

#### TBA

Regular Seminar Yang-Hui He (City U.)

 at: 14:00 QMWroom Room FB 1.06 abstract:

### 27.02.2014 (Thursday)

#### Aspects of 5d gauge theories

Regular Seminar Diego Rodriguez-Gomez (Oviedo U.)

 at: 14:00 QMWroom G.O. Jones 208 abstract: In this talk I will review recent progress in understanding aspects of 5d gauge theories. Under certain circumstances these can be at fixed points admitting a large N limit, whose gravity dual we will discuss. Such gravity dual suggests a yet more general class of quiver-type fixed point theories which can sometimes be understood in terms of S-duality. To this matter the braneweb construction of the theories will prove very helpful, yielding new insights which we will test using the 5d superconformal index.

format: plain


text:
# Polygons tree building by segments linking

Suppose a set of 2d polygons is given.

What I am trying to do is to link all the polygons together by segments in a such way that:

• each of the segments does not intersect any polygons in between (i.e. it connects the "visible" points of the polygon)
• the path along the segments from one polygon to another does not have any loops(if you consider polygons to be the nodes of the graph and the segments to be the edges then the graph has no cycles, i.e. there is a tree of polygons).

For example:

At the moment I am solving the problem by brute force search of the segments from each polygon to all the others checking if there is no intersections in between. And then I am using Kruskal algorithm to find a tree, so the path could be constructed. The solution is ok for "simple" polygons but quite time consuming for more complex ones when the number of vertices and polygons is big.

Are there similar problems or better solutions to this problem ?

This is not a direct hit on your problem (e.g., they allow the path to cross itself), but it illustrates the state of the art:

Polishchuk, Valentin, and Joseph SB Mitchell. "Touring Convex Bodies-A Conic Programming Solution." Cand. Conf. Comput. Geom. 2005. (PDF download.)

In particular: "Another open problem ([4]) is the hardness of touring a sequence of disjoint non-convex bodies in $\mathbb{R}^2$." So your problem is almost certainly unsolved.

And here is ref. [4]:

M. Dror, A. Efrat, A. Lubiw, and J. S. B. Mitchell. Touring a sequence of polygons. Proceedings 35th ACM Symposium on Theory of Computing, pages 473–482, 2003. ACM Press. (PDF talk slides.)

• Thanks for your answer! Sorry for such delay to accept it. I guess my initial description was too broad and your answer is the one which should be accepted. In order to solve the problem (a modified one actually) I used Voronoi diagram to construct proximity graph and extracted a spanning tree from it, so it could be traversed to find a path. Not sure if works in all kind of situations, but it worked out for me. Oct 5 '18 at 11:19


text:
## Monday, January 07, 2013

### SODA 2013: Part 3/n

I just attended Valerie King's talk on her paper with Bruce Kapron and Ben Mountjoy that does dynamic connectivity in worst-case polylog time (randomized). This paper received a Best Paper award (along with the Grohe et al paper on graph minors I mentioned yesterday).

The problem is a classic: given a stream of updates (edge insertions/deletions) to a graph, maintain a data structure that can answer "Are u and v connected" efficiently. There's been a slew of work on the problem: if you want worst-case bounds for updates, the best till now was $O(\sqrt{n})$ by Eppstein, Galil, Italiano and Nissenzweig (from 1992). There are polylogarithmic amortized bounds, but they can incur worst-case update times of $\Theta(n)$.

In this paper, after 20 years, they knock down the worst-case update times to polylogarithmic: the algorithms are randomized (with 1-sided error: it might occasionally declare two nodes disconnected when they were connected).

The idea itself is very elegant, and it connects to techniques in streaming algorithms in a way that I think is neat. WARNING: IANAE in this area, so my rendition might be slightly naïve, and is drawn from my understanding of Valerie King's excellent presentation.

The basic problem is this: I can maintain connectivity by maintaining a collection of trees. Adding an edge can be done without too much difficulty (indeed, if all you want to do is insert things, then you're back to union-find). It's insertion and deletion together that makes things hard: imagine that you delete an edge and disconnect a tree: you need to quickly determine if there's some other non-tree edge that can be used to reconnect the pieces, or if the two sides are now really disconnected.

More generally, consider the cutset maintainence problem. You have updates as before, but now a query is: given a set S, find a cut edge if one exists between S and V - S. It's not hard to see that this is the core routine you need for the tree.

The first elegant idea is this: suppose you represent each edge by a bit string consisting of the encoding of one endpoint followed by an encoding of the other. For example, the edge 2-3 might be written as 010011. Now for each vertex, compute the XOR of all the edges adjacent to it and call this its signature.

If you XOR all the signatures of vertices in a set, and if the set has exactly one cut edge, then what you get is the signature of that edge ! This is because each edge that's inside S will occur twice and therefore will zero out.

So this works if your cut set is of size 1. But suppose it's not ? Now you maintain $O(\log n)$ sets for each vertex. Each edge adjacent to the vertex is thrown into the $i^{\text{th}}$ set with probability $1/2^i$. With some appropriate duplication, you can show that if the cut set is of size $k$, then w.h.p the $\log k$th cut set will have exactly one element in it, and that's the element you can retrieve when you need to find a replacement edge.

There's a lot more technical work to do to get the whole algorithm working, and I won't go into that. But those of you who are familiar with streaming will recognize something here.

In essence, they've created a sketch for the set of edges adjacent to the vertex, and they have a way to represent the set compactly and retrieve individual elements from it. The trick with exponentially decaying levels is standard in streaming count estimation, and the GF(2) trick for storing the sketch is very similar to the trick used by Ahn, Guha and McGregor in their SODA 2012 paper on graph sketching.

And that's what I thought was the best part: that ideas that really have power in streaming can be used to help solve a longstanding open problem in graph algorithms. I should point out that the connection is post-facto: this paper was developed independently of the streaming work. But one does have to wonder what other connections we might be able to establish between sketching tricks on graphs and basic graph algorithms.


text:
# integration of $\int_0^{\frac{\pi}{2}} \cos^{n}(t)dt$

$$\int_0^{\frac{\pi}{2}}\cos^{n}(t)dt =?$$ To solve this problem, I was thinking that I would let $$\cos(t)= \frac{e^{it} + e^{-it}}{2}$$, then the integral will have the form: $$\int_0^{\frac{\pi}{2}} \left (\frac{e^{it} + e^{-it}}{2} \right)^{n}dt=\frac{1}{2^{n}}\,\sum_{k=0}^{n}\binom{n}{k}\int_0^{\frac{\pi}{2}}e^{i(n-2k)t}\,dt$$

From this point, I was stuck. So, would anyone please help me to walk through this problem.

• consider integration by parts and induction May 7, 2020 at 14:29
• See Wallis' integral. The article gives a method to evaluate this. May 7, 2020 at 14:32
• This is well known Wallis' integrals May 7, 2020 at 14:32

Use integration by parts on $$I(n)=\int_0^{\frac{\pi}{2}}\cos^{n}(t)dt=\int_0^{\frac{\pi}{2}}\cos(t)\cos^{n-1}(t)dt$$ then use the pythagorean identity on $$\sin^2(t)$$. You should end up with $$I(n)=\frac{n-1}{n}\int_0^{\frac{\pi}{2}}\cos^{n-2}(t)dt=\frac{n-1}{n}I(n-2)$$

• Thank you, In this way I will solve the question. May 7, 2020 at 15:09

$$\cos^n(t)=\sin^n\left(\frac{\pi}{2}-t\right)$$

Let:

$$\frac{\pi}{2}-t=x$$,

$$t=0 \implies x=\frac{\pi}{2}$$

$$t=\frac{\pi}{2} \implies x=0$$

$$\mathrm{d}t=-\mathrm{d}x$$

$$I=\int^{\frac{\pi}{2}}_0 \cos^n(t)~\mathrm{d}t=-\int^{\frac{\pi}{2}}_0 \sin^n(x)\mathrm{d}x=-\int^{\frac{\pi}{2}}_0 \sin (x)(1-\cos^2x)^{\frac{n-1}{2}}\mathrm{d}x$$

Now expand $$(1-\cos^2x)^{\frac{n-1}{2}}$$

You get a polynomial of form $$au'u^k$$, where $$u'=\sin(x)$$ and $$u^k=\cos^k$$ , which is integrable.

Well, my teacher gave us what is given below, without proof. If only this satisfies you, well and good, but if not, I'm gonna have to ask fellow members to help.

• Thank you, it is a reasonable answer for me. May 7, 2020 at 15:07
• I hope you understood the $1 or 2$ at the end of every bracketed term? May 7, 2020 at 15:13
• I know, it's okay. May 7, 2020 at 15:19


text:
Ask Your Question

# Revision history [back]

I don't completely understand why this is happening, but to work around it you can use the Polyhedron's projection method (the most flexible solution) or more simply the render_solid and render_wireframe methods. For example:

@interact
def _(t1=text_control("Polyhedron"), vertices="[[1,0],[0,1],[0,0]]"):
p=Polyhedron(vertices=eval(vertices))
show(p.render_solid(rgbcolor='green')+p.render_wireframe(rgbcolor='red'))


text:
# How can I show that the closure of the set $\Phi = \{1, 2, 3, 4,\ldots\}$ is the set itself?

If $\Phi \subseteq C(I)$, where $C(I)$ is the set of continuous real-valued functions on the interval $I=[0,1]$, and we define $\Phi = \{\phi_1, \phi_2,\phi_3,\ldots\}$ where

$1=\phi_1$, $2=\phi_2$, $\ldots$ , $k=\phi_k$, then the set $\Phi$ is unbounded.

How can I show that the closure of $\Phi$ is equal to itself? I have tried by assuming an arbitrary limit point and showing the limit point is contained in the set, but am running into a lot of difficult.

Extra Information: My motivation is that I know $\Phi$ is unbounded and hence NOT totally bounded. If $\Phi$ is NOT totally bounded, and the closure of $\Phi$ $= \Phi$, then I get that the closure of $\Phi$ is not totally bounded also, which by a certain theorem means the closure of $\Phi$ is NOT compact. So basically, I am trying to show non-compactness but am missing a crucial step. Help would be GREATLY appreciated!! Thanks!

• If you mean closed in the standard topology, then just look at any deleted neighborhood about each of the functions. If you choose your deleted neighborhood small enough, you'll see that it is in fact empty. This would say that there are no accumulation points. What then does that tell you? – Cameron Williams May 29 '14 at 12:46

## 2 Answers

Well, every compact subset of a metric space is totally bounded, and so bounded. So, all you really need to do is show that $\Phi$ is unbounded, from which non-compactness will follow by contrapositive.

Now, if you're trying to show that the closure of $\Phi$ is non-compact, then you will definitely need to prove that $\Phi$ is closed. To do so, suppose $\psi\in C(I)$ lies in the closure of $\Phi.$ Now, for any $\varepsilon>0$ there is necessarily some element of $\Phi$ lying within $\varepsilon$ of $\psi$--that is, some $\varphi\in\Phi$ such that $|\psi(x)-\varphi(x)|<\varepsilon$ for all $x\in I.$ In particular, fix any $\varepsilon_0\in\left(0,\frac12\right)$ and take $\varphi_k\in\Phi$ such that $|\psi(x)-\varphi_k(x)|<\varepsilon_0$ for all $x\in I,$ meaning that $$k-\frac12<k-\varepsilon_0<\psi(x)<k+\varepsilon_0<k+\frac12.$$ From this, we can see that if $j\ne k,$ then $\varphi_j$ is not within $\varepsilon_0$ of $\psi.$

Since there is a neighborhood of $\psi$ containing exactly one element of $\Phi,$ then $\psi$ is not a limit point of $\Phi$. But $\psi$ was an arbitrary element of the closure of $\Phi,$ so that means that $\Phi$ has no limit points! Do you see why $\Phi$ is then necessarily closed?

Consider the function $\operatorname{exp}(2\pi i\cdot)$ from $C(I)$ to the set of continuoos complex valued functions $C_{\mathbb{C}}(I)$ on $I$. Now, $\operatorname{exp}(2\pi i\cdot)$ is continuoos, and $C_{\mathbb{C}}(I)$ is T1, hence points are closed. This implies that $\operatorname{exp}(2\pi i\cdot)^{-1}(1)=\{\dots,-1,0,1,\dots\}$ is closed. Finally, $\{f\geq 0\}\subset C(I)$ is clearly closed, and $\Phi=\{\dots,-1,0,1,\dots\}\cap \{f\geq 0\}$.


text:
Question: Testing three-way interactions in DESeq2
2
20 months ago by
red_bricks20
red_bricks20 wrote:

Hi,

I am new to using DESeq2 and would appreciate some advice for a somewhat complex experimental design (for a non-statistician anyway). I have a dataset with 3 factor variables, each with 2 levels, as follows:

trt: control, treatment

geno: A, B

time: 6h, 12h (no time 0h)

Each combination of factor levels was replicated 3 times, giving 2 x 2 x 2 x 3 = 24 samples total.

Biologically, I want to find the genes that respond differently to treatment in the two genotypes; this can be a constant effect over time or not. Statistically, I figure that I should be looking for genes with significant geno x trt effect over time points, and also genes with significant geno x trt x time effect. Other ideas would be appreciated here.

Assuming the above reasoning makes sense, does the following code/design accomplish the goals above?

dds2 <- DESeqDataSetFromMatrix(countData = cts2,
colData = coldata,
design = ~ geno + trt + time + geno:trt + geno:time + trt:time + geno:trt:time)

dds2 <- DESeq(dds2, test="LRT", reduced = ~ geno + trt + time + geno:time + trt:time)

Also, what would the log2 fold change mean in this case?

modified 20 months ago by Michael Love24k • written 20 months ago by red_bricks20
Answer: Testing three-way interactions in DESeq2
2
20 months ago by
Michael Love24k
United States
Michael Love24k wrote:

"I want to find the genes that respond differently to treatment in the two genotypes; this can be a constant effect over time or not."

From what you've described, I think you want to use a full design of ~trt + geno + time + geno:time + trt:time + trt:geno:time

And then the reduced design is to remove the term trt:geno:time.

You can use resultsNames() to see the names of the coefficients after fitting the model.

There will be two coefficients associated with the interaction term, a difference between the genotypes due to treatment at time 1 and another for the difference at time 2. You can pull these out with results() using 'name'.

Hi Michael,

I just wanted to confirm that the test as you have described will produce P-values for difference in response to treatment between the two genotypes regardless of whether this effect changes or not at the two time points. Is that correct?

So I would not need to pull out the two coefficients associated with trt:geno:time unless I wanted to do Wald tests for trt:geno effects at time 1 and time 2 individually or if I wanted to retrieve the fold changes for visualization.

Thanks again!

1

Because you have two interaction terms that are dropped from full in the reduced design, yes, it will give small p-values whether there is a difference in treatment across genotype at time 1 or time 2 or both.

Yes to second question.


text:
## The Annals of Statistics

### Estimation for Autoregressive Processes with Unit Roots

#### Abstract

Let $Y_t$ satisfy the stochastic difference equation $Y_t = \sum^p_{j = 1}\eta_jY_{t - j} + e_t$ for $t = 1, 2, \cdots$, where the $e_t$ are independent identically distributed $(0, \sigma^2)$ random variables and the initial conditions $(Y_{-p + 1}, Y_{-p + 2}, \cdots, Y_0)$ are fixed constants. It is assumed the true, but unknown, roots $m_1, m_2, \cdots, m_p$ of $m^p - \sum^p_{j = 1}\eta_jm^{p - j} = 0$ satisfy $m_1 = m_2 = 1$ and $|m_j| < 1$ for $j = 3, 4, \cdots, p$. Let $\hat{\mathbf{\eta}}$ denote the least squares estimator of $\mathbf{\eta} = (\eta_1, \eta_2, \cdots, \eta_p)'$ obtained by the least squares regression of $Y_t$ on $Y_{t - 1}, Y_{t - 2}, \cdots, Y_{t - p}$ for $t = 1, 2, \cdots, n$. The asymptotic distributions of $\hat{\mathbf{\eta}}$ and of a test statistic designed to test the hypothesis that $m_1 = m_2 = 1$ are characterized. Analogous distributional results are obtained for models containing time trend and intercept terms. Estimated percentiles for these distributions are obtained by the Monte Carlo method.

#### Article information

Source
Ann. Statist., Volume 7, Number 5 (1979), 1106-1120.

Dates
First available in Project Euclid: 12 April 2007

https://projecteuclid.org/euclid.aos/1176344793

Digital Object Identifier
doi:10.1214/aos/1176344793

Mathematical Reviews number (MathSciNet)
MR536511

Zentralblatt MATH identifier
0419.62068

JSTOR


text:
# sklearn.preprocessing.Normalizer¶

class sklearn.preprocessing.Normalizer(norm='l2', *, copy=True)[source]

Normalize samples individually to unit norm.

Each sample (i.e. each row of the data matrix) with at least one non zero component is rescaled independently of other samples so that its norm (l1, l2 or inf) equals one.

This transformer is able to work both with dense numpy arrays and scipy.sparse matrix (use CSR format if you want to avoid the burden of a copy / conversion).

Scaling inputs to unit norms is a common operation for text classification or clustering for instance. For instance the dot product of two l2-normalized TF-IDF vectors is the cosine similarity of the vectors and is the base similarity metric for the Vector Space Model commonly used by the Information Retrieval community.

Read more in the User Guide.

Parameters
norm‘l1’, ‘l2’, or ‘max’, optional (‘l2’ by default)

The norm to use to normalize each non zero sample. If norm=’max’ is used, values will be rescaled by the maximum of the absolute values.

copyboolean, optional, default True

set to False to perform inplace row normalization and avoid a copy (if the input is already a numpy array or a scipy.sparse CSR matrix).

normalize

Equivalent function without the estimator API.

Notes

This estimator is stateless (besides constructor parameters), the fit method does nothing but is useful when used in a pipeline.

For a comparison of the different scalers, transformers, and normalizers, see examples/preprocessing/plot_all_scaling.py.

Examples

>>> from sklearn.preprocessing import Normalizer
>>> X = [[4, 1, 2, 2],
...      [1, 3, 9, 3],
...      [5, 7, 5, 1]]
>>> transformer = Normalizer().fit(X)  # fit does nothing.
>>> transformer
Normalizer()
>>> transformer.transform(X)
array([[0.8, 0.2, 0.4, 0.4],
[0.1, 0.3, 0.9, 0.3],
[0.5, 0.7, 0.5, 0.1]])

Methods

 fit(X[, y]) Do nothing and return the estimator unchanged fit_transform(X[, y]) Fit to data, then transform it. get_params([deep]) Get parameters for this estimator. set_params(**params) Set the parameters of this estimator. transform(X[, copy]) Scale each non zero row of X to unit norm
__init__(norm='l2', *, copy=True)[source]

Initialize self. See help(type(self)) for accurate signature.

fit(X, y=None)[source]

Do nothing and return the estimator unchanged

This method is just there to implement the usual API and hence work in pipelines.

Parameters
Xarray-like
fit_transform(X, y=None, **fit_params)[source]

Fit to data, then transform it.

Fits transformer to X and y with optional parameters fit_params and returns a transformed version of X.

Parameters
X{array-like, sparse matrix, dataframe} of shape (n_samples, n_features)
yndarray of shape (n_samples,), default=None

Target values.

**fit_paramsdict

Returns
X_newndarray array of shape (n_samples, n_features_new)

Transformed array.

get_params(deep=True)[source]

Get parameters for this estimator.

Parameters
deepbool, default=True

If True, will return the parameters for this estimator and contained subobjects that are estimators.

Returns
paramsmapping of string to any

Parameter names mapped to their values.

set_params(**params)[source]

Set the parameters of this estimator.

The method works on simple estimators as well as on nested objects (such as pipelines). The latter have parameters of the form <component>__<parameter> so that it’s possible to update each component of a nested object.

Parameters
**paramsdict

Estimator parameters.

Returns
selfobject

Estimator instance.

transform(X, copy=None)[source]

Scale each non zero row of X to unit norm

Parameters
X{array-like, sparse matrix}, shape [n_samples, n_features]

The data to normalize, row by row. scipy.sparse matrices should be in CSR format to avoid an un-necessary copy.

copybool, optional (default: None)

Copy the input X or not.


text:
# Difference in Difference with control - common trend interpretation

I have a question concerning the interpretation of the common trend assumption in a very specific case of diff-in-diff. I am using a panel to find the effect of a treatment (on houesehold level) on the number of years of schooling of individuals. The regression I use is $$\text{yrschl}_{it} = \beta_0 + \beta_1 \text{treatment}_h + \beta_2 \text{after}_t + \beta_3 (\text{treatment}_h \cdot \text{after}_t) + \gamma X_{iht} + \epsilon_{iht}$$ and I cluster the standard errors at the household level.

As there has been no randomization across the two groups, I use control variables as $\text{sex}_{it}$, $\text{age}_{it}$, $\text{age}^2_{it}$, $\text{mother's education}_{it}$, $\text{father's education}_{it}$ and $\text{urban/rural area}_{iht}$.

My question now is how to interpret the ceteris paribus condition jointly with the common trend assumption. In particular, my doubt concerns the ceteris paribus condition related to age.

How do I have to formulate the common trend assumption in this case?

Is it that, IN ABSENCE OF THE TREATMENT, the change in the average number of years of schooling of the children who are, e.g. 14 years old in $t=0$ and therefore 20 years old in $t=1$ (I only have data for 6 years later) and belong to the treatment group is the same as the one of those children who were 14 in $t=0$ and 20 in $t=1$ and are untreated?

Or does it rather mean that, IN ABSENCE OF THE TREATMENT, the change in the average years of schooling between treated 14 years old children in $t=0$ and treated 14 years old children in $t=1$ is the same as the one between untreated 14 years old children in $T=0$ and untreated 14 years old children in $t=1$? Does the ceteris paribus condition hold across time periods? Since I am using a balanced panel, there would be only observations for young individuals in $t=0$ and not in $t=1$ (as they got 6 years older in the meanwhile). This speaks against this second interpretation, isn't it?

• What is the treatment and when does it kick in? – Andy Aug 1 '15 at 10:19
• treatment is 1 if the individual belongs to a household in which there is a migration happening for the first time between t=0 and t=1 while it is 0 if until t=1 in households who never faced a migration. After_t is equal to 1 if t=1 and equal to 0 if t=0. P.s. I have edited my question because I forgot to write "IN ABSENCE OF THE TREATMENT" when interpreting the common trend assumption. – Gio Aug 1 '15 at 11:16

When your treatment status depends on (fully!) observed covariates the parallel trends assumption does not depend anymore on the unconditional but the conditional pre-treatment trends. If you were to state the identification assumption in a paper, you would write something like:

The identifying assumption is that pre-treatment trends in the outcome for treated and untreated households are parallel conditional on observables that determine treatment status. This means that treated and control households' outcomes with similar characteristics would have continued in a parallel way in the post-treatment period in the absence of the treatment.

Since you only have one pre-treatment period it is somewhat odd to speak about pre-treatment trends though. There is no way that you can infer those from a single data point but the required condition would be the one cited. For your case you are conditioning on the baseline period ($t=0$) characteristics.

Typically it is very difficult to sell a difference in differences framework if you cannot show these trends but if this is for an assignment or thesis work then it should be sufficient that you demonstrate your awareness of this problem. Even though it is not asked for in the question I still want to hint to one or two more points that you might want to think about:

• migration is a decision of the household and I highly doubt that this decision is fully captured by observables; in this case you might want to instrument the treatment status with some policy change (or another valid instrument) that affects the migration decision but not the educational outcomes
• depending on the country you are looking at, education is bounded below by minimum school leaving ages. Suppose your treatment would have a negative effect on years of education you may not be able to find this causal effect if observed educational outcomes cannot go any lower in response to treatment because of compulsory schooling laws

As a minor point you also may want to revisit the subscripts for mother's and father's education. Typically those do not change anymore after people have completed their formal education, i.e. they shouldn't have a time subscript.

• Thanks! In fact, I do have another period, which is 8 years before t=0. However, not all individuals were present/ at school in all three periods (Actually, when adopting the strategy described above, I limit the sample to those who were enrolled at school in t=0). So, even if I can test the common trend assumption, I only can do so for a subset of individuals which leads to a very low number of treated individuals. Therefore, even if I get a non-significant interaction coefficient when doing the placebo test (by changing after_t), it is likely to be due to the large standard errors, right? – Gio Aug 1 '15 at 16:19
• Moreover,if the interpretation of the common trend assumption is the above suggested one,then what is the difference between a simple OLS and a DiD?I know that the OLS assumes the same level of years of schooling across groups while the DiD only assumes the same trend,however,in the specific case of years of schooling,what does this difference exactly mean?Why should treated and control have different levels but the same trend?Is it like saying that we weaken the assumption by allowing, e.g. one group to start school later,but then, once started,the schooling behavior is similar? – Gio Aug 1 '15 at 16:29
• For that you might this other answer useful which explains the common trends assumption: stats.stackexchange.com/questions/152138/… – Andy Aug 1 '15 at 16:59
• Thanks for the link.Actually, I know the difference between the DiD and the OLS, but the problem is the specificity of my dependent variable years of schooling. Assuming that there is a common trend in years of schooling means that,even if the average of both groups is different, its development over time is similar.But how do you interpret the development over time of years of schooling?If this must be similar, then it is logic to think that their behavior with respect to education is similar and thus there should be no reason to have different levels of education(if there was no treatment!). – Gio Aug 1 '15 at 17:39
• It's like the issue I raised regarding the compulsory schooling laws. Suppose you follow two kids of equal age in the base period for 3 years where treatment occurs between year 2 and 3. Say from year one to two they increase schooling by 1. In year three the treated kid quits school because of the treated whereas the control kids increases again by 1 year, which would have happened to the treated kid too in the absence of the treatment. – Andy Aug 1 '15 at 17:44

Another thing:

I belive that put control variables that are invariant in the time (like sex and father/mother education) don´t have any sense. Your especification already considers time invariant factors.


text:
# Mölkky

Mölkky is a Finnish throwing game. The players use a wooden pin (also called "mölkky") to try to knock over wooden pins of almost similar dimensions with the throwing pin, marked with numbers from 1 to 12. The initial position of the pins is as follows:

   (07)(09)(08)
(05)(11)(12)(06)
(03)(10)(04)
(01)(02)

This description and the rules below are based on Wikipedia.

# Simplified Mölkky rules

1. Knocking over one pin scores the number of points marked on the pin.

2. Knocking 2 or more pins scores the number of pins knocked over (e.g., knocking over 3 pins scores 3 points).

3. The aim of the game is to reach exactly 50 points. Scoring more than 50 is penalized by setting the score back to 25 points.

4. For the purpose of this challenge, we will make the assumption that the pins are always in the exact order described above. (In a real game, the pins are stood up again after each throw in the location where they landed.)

All other Mölkky rules are ignored and only a single player is considered.

# Input

A non-empty list of lists of 12 booleans. Each list of booleans describes the outcome of a throw: 1 if the pin was knocked over and 0 otherwise. The booleans are given in the exact order of the pins, from top left to bottom right: 7, 9, 8, 5, 11, 12, 6, 3, 10, 4, 1, 2.

# Output

The score after all throws described in the input, calculated by applying rules 1, 2 and 3.

# Detailed example

Let's consider the following input:

// 07 09 08 05 11 12 06 03 10 04 01 02
[ [ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ],  // scores 5 (rule #1)
[ 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ],  // scores 2 (rule #2), total: 7
[ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1 ],  // scores 7, total: 14
[ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ],  // scores 12, total: 26
[ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ],  // scores 12, total: 38
[ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ],  // scores 11, total: 49
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],  // scores 7, total: 56 -> 25 (rule #3)
[ 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ] // scores 2, total: 27

The expected output is 27.

# Challenge rules

• You may take input in any reasonable format. Instead of lists of booleans, you can use integers where the most significant bit is the pin #7 and the least significant bit is the pin #2. In this format, the above example would be passed as [ 256, 2304, 127, 64, 64, 128, 2048, 3072 ].
• The input list may contain throws where no pin at all is knocked over, in which case the score is let unchanged.
• You don't have anything special to do when the score reaches exactly 50 points. But you can assume that no other throw will follow when it happens.
• This is , so the shortest answer in bytes wins.

# Test cases

Using lists of integers as input:

[ 0 ] --> 0
[ 528 ] --> 2
[ 4095 ] --> 12
[ 64, 0, 3208 ] --> 16
[ 16, 1907, 2048 ] --> 18
[ 2023, 2010, 1, 8 ] --> 29
[ 1726, 128, 35, 3136, 1024 ] --> 34
[ 32, 32, 2924, 2, 256, 16 ] --> 28
[ 64, 64, 2434, 1904, 3251, 32, 256 ] --> 25
[ 3659, 2777, 2211, 3957, 64, 2208, 492, 2815 ] --> 25
[ 2047, 1402, 2, 2599, 4, 1024, 2048, 3266 ] --> 50
[ 256, 2304, 127, 64, 64, 128, 2048, 3072 ] --> 27
[ 16, 8, 128, 1, 2048, 1, 2048, 513, 8, 3206 ] --> 30

You can follow this link to get these test cases in Boolean format.

• Cool challenge, and also a great game to play in the summer for those of you who haven't tried it out — works great along with a grill. – Nit May 6 '18 at 22:31
• @Nit Thank you. :) I have to confess that I didn't know this game until today. I saw people playing it while walking in a park this afternoon. Now, I'd like to give it a try. – Arnauld May 6 '18 at 22:35

# Python 2, 126 111 108 104 bytes

-3 bytes thanks to Jonathan Allan

-4 bytes thanks to Kaya!

f=lambda A,t=0:t>50and f(A,25)or A and f(A[1:],t-~(sum(A[0])-1or 762447093078/12**A[0].index(1)%12))or t

Try it online!

Defines a recursive function that takes a 2D array of 1s and 0s and returns an integer value. Nothing too special in the construction, and I'm sure there's a simpler solution.

### Explanation:

f=lambda A,t=0:    #Define the function, initialising t to 0 on the first iteration
t>50and f(A,25)      #If t>50 then iterate again with t=25
or    #Else
A and                #If A exists
f(A[1:],       #Iterate again without the first list of A
t-~         #And add to t, either
(sum(A[0])-1   #The sum of all elements if that's not 1
or
762447093078/12**A[0].index(1)%12   #Else the appropriate pin value (black magic!)
or t       #Finally, if A is finished, just return t

• (0x103925BA4786>>4*A[0].index(1))%16 saves 1 character versus ord('GIHEKLFCJDAB'[A[0].index(1)])-65 – Kaya May 7 '18 at 4:58
• A little more optimal: 762447093078/12**A[0].index(1)%12 – Kaya May 7 '18 at 5:06
• That stuff looks like black magic to me! Thanks @Kaya! – Jo King May 7 '18 at 7:14
• That's just encoding with base 12 – enedil May 7 '18 at 13:01

# Jelly, 25 bytes

“ñ€bḷ’œ?TLḢṖ?µ€+25¹>?50ɗ/

A monadic link accepting a list of lists of ones and zeros (each of length 12) which returns an integer.

Try it online! Or see the test-suite (using the integer values given in the OP)

### How?

This solution makes use of, œ?, which given a number, n, and a list finds the nth lexicographical permutation of the list where the list defines the sort order. First we need to work out this n:

 index:  1  2  3  4  5  6  7  8  9 10 11 12
value:  7  9  8  5 11 12  6  3 10  4  1  2   (as defined by the question)
P: 11 12  8 10  4  7  1  3  2  9  5  6   (our permutation lookup array)

...that is, P at index i is set to the original index of the value i.
This P has a lexicographical index of 438,337,469 (that is, if you took all 12! permutations of the numbers 1 to 12 and sorted them lexicographically, the 438,337,469th would be P).
This may be found using Jelly's Œ¿ atom.
Both steps may be performed in one go using the Jelly program ĠŒ¿

“ñ€bḷ’œ?TLḢṖ?µ€+25¹>?50ɗ/ - Link: list of lists of zeros and ones
µ€           - perform the monadic chain to the left for €ach list:
“ñ€bḷ’                    -   base 250 number = 438337469
œ?                  -   nth permutation (reorder the 1s and 0s to their pin values)
T                 -   truthy indices (get the pin values of the 1s)
?             -   if...
Ṗ              -   ...condition: pop (length greater than 1 ?)
L                -   ...then: length (the number of pins)
Ḣ               -   ...else: head (the first (& only) pin value)
/ - reduce the resulting list of integers with:
ɗ  -   last three links as a dyad:
+          -     addition (add the two values together)
50   -     literal fifty
?     -     if...
>      -     ...condition: greater than (sum greater than 50 ?)
25        -     ...then: literal twenty-five
¹       -     ...else: identity (do nothing - just yield the sum)

• I think your explanation about finding the appropriate lexicographical index among all permutations would be worth adding as a Jelly tip. (Last time I had to do that, I did a manual dichotomic search, which is not that long for short sequences but ... kinda tedious. ^^) – Arnauld May 7 '18 at 10:32
• LOL; I had exactly the same solution, except for two different bytes: Ṗ -> Ḋ, µ -> Ʋ. Jelly would really benefit from acceppting a niladic link as ¡'s <link> (first argument), except that, if on the very start of the program, keep the special-casing behavior. – Erik the Outgolfer May 7 '18 at 15:05
• ...and I almost used both! – Jonathan Allan May 7 '18 at 15:07

# Python 2, 90 bytes

Heavily inspired by Jo King's Python 2 answer and utilising Kaya's base-12 representation comment

t=0
for v in input():t+=sum(v)-1or 762447093078/12**v.index(1)%12;t=[t+1,25][t>49]
print t

Try it online! Or see the test-suite

# Pyth, 5148 38 bytes

VQI>=+Z?qJsN1@.PC"îO&"S12xN1J50=Z25;Z

Saved 10 bytes thanks to Jonathan Allan Takes input as a list of lists of booleans.
Try it here

### Explanation

VQI>=+Z?qJsN1@.PC"îO&"S12xN1J50=Z25;Z
VQ                                  ;     For each input...
=+Z                                   ... add to the total...
?q sN1                             ... if one pin is down...
@.PC"îO&"S12xN1              ... the score of that pin.
J                    J           ... otherwise, the count.
I>                           50         If we pass 50...
=Z25     ... reset to 25.
Z    Output the total.

• Not sure how to get it into the program exactly, but it should save 6 or 7 bytes if you can... 7tT8h4hT12h5h2T4h02 -> .PC"îO&"S12 - uses lexicographical permutation indexing like my Jelly answer. (The code has an unprintable byte of 0x0F at the start of the string.) – Jonathan Allan May 7 '18 at 2:46
• )) can be ; – Jonathan Allan May 7 '18 at 2:58

# 05AB1E, 29 28 bytes

v•CÞŸαLć•13вyOΘmyÏOO25‚¬50›è

Try it online!

Explanation

v                              # for each boolean list in input
•CÞŸαLć•                      # push 13875514324986
13в                   # convert to a list of base-13 numbers
yO                 # push the sum of y
Θm               # truthify and raise the pin-list to this number (0 or 1)
yÏ             # keep those which are true in the current list
OO           # sum the list and the stack
25‚        # pair with 25
¬50›    # check if the first number is larger than 50
è   # index into the pair with this result

$\+=y/1//-1||/1/g&&(0,6,8,7,4,10,11,5,2,9,3,0,1)[pos];$\=25if++$\>50}{  Try it online! Takes input as a series of newline separated bitstrings. # Haskell, 96 bytes foldl(\s a->([s..50]++e)!!sum(last$zipWith(*)[7,9,8,5,11,12,6,3,10,4,1,2]a:[a|sum a>1]))0
e=25:e

Try it online!

The wrapping is clever: I essentially index at position s+sum(…) into the list ([0..50]++cycle[25]). However, a shorter way to write that is indexing at position sum(…) and beginning the list at s.

# Java 10, 131130 129 bytes

m->{int r=0,i,s,t;for(var a:m){for(i=s=t=0;i<12;s+=a[i++])t=a[i]>0?"    \n".charAt(i):t;r+=s<2?t:s;r=r>50?25:r;}return r;}

Contains 10 unprintables.
Input as integer-matrix of zeros and ones.

-1 byte thanks to @JonathanFrech, changing \t into an actual tab (works in TIO, doesn't work in my local IDE).

Try it online.

Explanation:

m->{                // Method with integer-matrix parameter and integer return-type
int r=0,          //  Result-integer, starting at 0
i,s,t;        //  Temp integers
for(var a:m){     //  Loop over the integer-arrays of the input
for(i=s=t=0;    //   Reset i, s and t to 0
i<12;       //   Loop i in the range [0,12)
s+=a[i++])  //    Increase s by the current value (0 or 1)
t=a[i]>0?     //    If the current value is 1:
"  \n".charAt(i)
//     Set t to the score at this position
:t;         //    Else: Leave t the same
r+=s<2?         //   If only a single pin was hit:
t           //    Add its score t to the result
:            //   Else:
s;          //    Add the amount of pins s to the result
r=r>50?         //   If the result is now above 50
25           //    Penalize it back to 25
:r;}          //   If not, it stays the same
return r;}        //  Return the result

• I think you can save one byte by using an actual tab character in "\t\n". – Jonathan Frech May 7 '18 at 10:14
• @JonathanFrech Hmm, indeed seems to work in TIO. Doesn't work locally in my IDE, but who cares about that I guess.. ;) – Kevin Cruijssen May 7 '18 at 10:27
• When there is a working implementation somewhere, it is allowed. :@ – Jonathan Frech May 7 '18 at 11:59

# Charcoal, 43 bytes

≔⁰ηＦθ«≧⁺⎇⊖ΣιΣι⌕α§”$｜#z⁸Ｕg⊗”⌕ι¹η¿›η⁵⁰≔²⁵η»Ｉη  Try it online! Link is to verbose version of code. Takes input as a boolean array. Explanation: ≔⁰η  Set the score to 0. Ｆθ«  Loop over the throws. ⎇⊖Σι  Is the number of pins 1? Σι  If not, then take the number of pins. ⌕α§”$｜#z⁸Ｕg⊗”⌕ι¹

Otherwise, translate the position of the pin to a value.

≧⁺...η

Add it to the score.

¿›η⁵⁰≔²⁵η

If the score exceeds 50 then set it back to 25.

»Ｉη

Print the final result after all the throws.

# Haskell, 110 bytes

m s|sum s==1=sum$zipWith(*)[7,9,8,5,11,12,6,3,10,4,1,2]s|1>0=sum s f l=foldl(\b->c.(b+).m)0l c a|a>50=25|1>0=a  Same length: f l=foldl(\b a->last$b+m a:[25|b+m a>50])0l instead of f and c

Try it online!

• Drop the l argument in f for 3 bytes. f=foldl(\b->c.(b+).m)0 – aoemica May 11 '18 at 1:14

# Husk, 47 35 bytes

-12 bytes thanks to H.PWiz (better way of generating the list encoding points)!

F₅0
S?25>50+?←Lεf+Nm+3d4652893071

Try it online!

### Explanation

F₅0  -- input is a list of boolean lists
F    -- left fold by
₅   -- | the function flipped (overflowing label) on line 1
0  -- | with initial value 0

S?25>50+?←Lεf+Nm+3d4652893071  -- example inputs: [0,0,0,1,0,0,0,0,0,0,0,0] 0
4652893071  -- integer literal: 4652893071
d            -- digits: [4,6,5,2,8,9,3,0,7,1]
m+3             -- map (+3): [7,9,8,5,11,12,6,3,10,4]
+N                -- append natural numbers: [7,9,8,5,11,12,6,3,10,4,1,2,3,...
f                   -- filter this list by argument: [5]
?  ε                     -- if it's of length 1
←                       -- | take first
L                      -- | else the length
-- : 5
+                         -- add to argument: 5
?  >50                          -- if the value is > 50
25                             -- | then 25
S                                -- | else the value
-- : 5

• How about m+3d4652893071? – H.PWiz May 7 '18 at 0:35

# Red, 189 172 bytes

func[b][s: 0 foreach c b[d: 0 foreach e c[if e = 1[d: d + 1]]i: find c 1
n: either i[pick[7 9 8 5 11 12 6 3 10 4 1 2]index? i][0]if 50 < s: s + either 1 < d[d][n][s: 25]]s]

Try it online!

## Explanation of the ungolfed code:

f: func[b][                                            ; a block of blocks of booleans
s: 0                                               ; sets sum to 0
foreach c b[                                       ; for each row of booleans
d: 0 foreach e c[if e = 1[d: d + 1]            ; count the number of 1s
i: find c 1                                    ; the index of the first 1
n: either i[pick [7 9 8 5 11 12 6 3 10 4 1 2]  ; if there is 1, pick the number
index? i][0]                       ; at the index of 1
; otherwise 0
if 50 < s: s + either 1 < d[d][n][s: 25]       ; if there is only one 1, add
; the number to the sum, otherwise
; the number of 1s
; if the sum > 50, reset it to 25
]
s                                                  ; return the sum
]

# JavaScript (ES6), 98 bytes

a=>a.map(b=>b.map((m,i)=>(c+=m,d+=m*('0x'+'7985bc63a412'[i])),c=d=0)|(t+=c>1?c:d)>50?t=25:0,t=0)|t

Test cases:

f=
a=>a.map(b=>b.map((m,i)=>(c+=m,d+=m*('0x'+'7985bc63a412'[i])),c=d=0)|(t+=c>1?c:d)>50?t=25:0,t=0)|t

console.log(f([ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ])) // 0

console.log(f([ [ 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0 ] ])) // 2

console.log(f([ [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ])) // 12

console.log(f(
[ [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 ] ]
)); // 16

console.log(f(
[ [ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 ],
[ 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1 ],
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
])); // 18

console.log(f(
[ [ 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 ],
[ 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 ] ]
)); // 29

console.log(f(
[ [ 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0 ],
[ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1 ],
[ 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ],
[ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ]
))  // 34

console.log(f(
[ [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ],
[ 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 ],
[ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 ] ]
))  // 28

console.log(f(
[ [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ],
[ 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0 ],
[ 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0 ],
[ 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1 ],
[ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ] ]
))  // 25

console.log(f(
[ [ 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1 ],
[ 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1 ],
[ 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1 ],
[ 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1 ],
[ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ],
[ 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0 ],
[ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 ] ]
)) // 25

console.log(f(
[ [ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
[ 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 ],
[ 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 ],
[ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0 ] ]
)) // 50

console.log(f(
[ [ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1 ],
[ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ],
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ]
)) // 27

console.log(f(
[ [ 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 ],
[ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ],
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ],
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 ],
[ 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0 ] ]
)) // 30

• Same size as (and very similar to) my reference implementation. :) – Arnauld May 8 '18 at 20:14
• Ah, cool. I'm happy whenever I can match your code size. It's only once in a blue moon that I can beat it :) – Rick Hitchcock May 8 '18 at 20:20

# Stax, 37 bytes

├T<↓"♥←~;▌6»≥øF←î5░U╚_π○Q▒<│∟└ù║pε♀▀æ

Run and debug it

Try It online!

Explanation

F:1"=EA5MQ9-I1%)"!s@c%1={h+}{%+}?c50>{d25}{}?    # Full program, unpacked

F                                                # Loop through every element
:1                                              # Get indices of truthy elements
"=EA5MQ9-I1%)"!                               # Push encoded [7,9,8,5,11,12,6,3,10,4,1,2]
s@                              # Swap the top 2 elements of stack and get elements at indexes
c%1=                          # Copy the top element, get length of array, compare to length of 1
{h+}{%+}?                 # If it has length of 1, add the element, otherwise add the length of the array to total
c50>            # Compare total to 50,
{d25}{}?    # If it is greater, pop it off and push 25 to reset counter, otherwise do nothing

Not my best work, but it works. I'm sure there is somehting I'm missing to make it a bit shorter.

# Python 2, 109105 103 bytes

c=0
for l in input():a=sum(l);c+=int('7985bc63a412'[l.index(1)],16)if a==1else a;c=(25,c)[c<51]
print c

Try it online!

Alternative without a recursive function.

-2 with thanks to @Jo King

• You can remove the brackets around the string literal – Jo King May 7 '18 at 22:15


text:
# Why the surge of interest in math?

By Murray Bourne, 21 Aug 2006

I did a Technorati search on the term "math". I am intrigued why there was a surge of interest in posts containing "math" on May 25/26 and during the first 10 days of June 2006.

Was it the beginning of a new series of Numb3rs, or something?

Here is the graph showing the surge: (Source: Technorati, 21 Aug 2006)

Unfortunately, Technorati no longer provides these charts. It's a shame.

Alternatively, here's the result for "math" on Google Trends.

Be the first to comment below.

### Comment Preview

HTML: You can use simple tags like <b>, <a href="...">, etc.

To enter math, you can can either:

1. Use simple calculator-like input in the following format (surround your math in backticks, or qq on tablet or phone):
a^2 = sqrt(b^2 + c^2)
(See more on ASCIIMath syntax); or
2. Use simple LaTeX in the following format. Surround your math with $$ and $$.
$$\int g dx = \sqrt{\frac{a}{b}}$$
(This is standard simple LaTeX.)

NOTE: You can mix both types of math entry in your comment.


text:
# Connexions

You are here: Home » Content » Region of Convergence for the Z-transform

### Recently Viewed

This feature requires Javascript to be enabled.

### Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.

# Region of Convergence for the Z-transform

Module by: Benjamin Fite. E-mail the author

Summary: (Blank Abstract)

Note: You are viewing an old version of this document. The latest version is available here.

## The Region of Convergence

The region of convergence, known as the ROC, is important to understand because it defines the region where the z-transform exists. The z-transform of a sequence is defined as

Xz= n =xnzn Xz n x n z n
(1)
The ROC for a given xn x n , is defined as the range of z z for which the z-transform converges. Since the z-transform is a power series, it converges when xnzn x n z n is absolutely summable. Stated differently,
n =|xnzn|< n x n z n
(2)
must be satisfied for convergence.

## Properties of the Region of Convergencec

The Region of Convergence has a number of properties that are dependent on the characteristics of the signal, xn x n .

• The ROC cannot contain any poles. By definition a pole is a where Xz X z is infinite. Since Xz X z must be finite for all zz for convergence, there cannot be a pole in the ROC.
• If xn x n is a finite-duration sequence, then the ROC is the entire z-plane, except possibly z=0 z 0 or |z|= z . A finite-duration sequence is a sequence that is nonzero in a finite interval n 1 n n 2 n 1 n n 2 . As long as each value of xn x n is finite then the sequence will be absolutely summable. When n 2 >0 n 2 0 there will be a z-1 z term and thus the ROC will not include z=0 z 0 . When n 1 <0 n 1 0 then the sum will be infinite and thus the ROC will not include |z|= z . On the other hand, when n 2 0 n 2 0 then the ROC will include z=0 z 0 , and when n 1 0 n 1 0 the ROC will include |z|= z . With these constraints, the only signal, then, whose ROC is the entire z-plane is xn=cδn x n c δ n .

The next properties apply to infinite duration sequences. As noted above, the z-transform converges when |Xz|< X z . So we can write

|Xz|=| n =xnzn| n =|xnzn|= n =|xn||z|n X z n x n z n n x n z n n x n z n
(3)
We can then split the infinite sum into positive-time and negative-time portions. So
|Xz|Nz+Pz X z N z P z
(4)
where
Nz= n =-1|xn||z|n N z n -1 x n z n
(5)
and
Pz= n =0|xn||z|n P z n 0 x n z n
(6)
In order for |Xz| X z to be finite, |xn| x n must be bounded. Let us then set
|xn| C 1 r 1 n x n C 1 r 1 n
(7)
for n<0 n 0 and
|xn| C 2 r 2 n x n C 2 r 2 n
(8)
for n0 n 0 From this some further properties can be derived:
• If xn x n is a right-sided sequence, then the ROC extends outward from the outermost pole in Xz X z . A right-sided sequence is a sequence where xn=0 x n 0 for n< n 1 < n n 1 . Looking at the positive-time portion from the above derivation, it follows that
Pz C 2 n =0 r 2 n|z|n= C 2 n =0 r 2 |z|n P z C 2 n 0 r 2 n z n C 2 n 0 r 2 z n
(9)
Thus in order for this sum to converge, |z|> r 2 z r 2 , and therefore the ROC of a right-sided sequence is of the form |z|> r 2 z r 2 .

• If xn x n is a left-sided sequence, then the ROC extends inward from the innermost pole in Xz X z . A right-sided sequence is a sequence where xn=0 x n 0 for n> n 2 > n n 2 . Looking at the negative-time portion from the above derivation, it follows that
Nz C 1 n =-1 r 1 n|z|n= C 1 n =-1 r 1 |z|n= C 1 k =1|z| r 1 k N z C 1 n -1 r 1 n z n C 1 n -1 r 1 z n C 1 k 1 z r 1 k
(10)
Thus in order for this sum to converge, |z|< r 1 z r 1 , and therefore the ROC of a left-sided sequence is of the form |z|< r 1 z r 1 .

• If xn x n is a two-sided sequence, the ROC will be a ring in the z-plane that is bounded on the interior and exterior by a pole. A two-sided sequence is an sequence with infinite duration in the positive and negative directions. From the derivation of the above two properties, it follows that if r 2 <|z|< r 2 r 2 z r 2 converges, then both the positive-time and negative-time portions converge and thus Xz X z converges as well. Therefore the ROC of a two-sided sequence is of the form r 2 <|z|< r 2 r 2 z r 2 .

## Examples

To gain further insight it is good to look at a couple of examples.

### Example 1

Lets take

x 1 n=12nun+14nun x 1 n 1 2 n u n 1 4 n u n
(11)
The z-transform of 12nun 1 2 n u n is zz12 z z 1 2 with an ROC at |z|>12 z 1 2 .

The z-transform of -14nun -1 4 n u n is zz+14 z z 1 4 with an ROC at |z|>-14 z -1 4 .

Due to linearity,

X 1 z=zz12+zz+14=z(2z18)(z12)(z+14) X 1 z z z 1 2 z z 1 4 z 2 z 1 8 z 1 2 z 1 4
(12)
By observation it is clear that there are two zeros, at 0 0 and 116 1 16 , and two poles, at 12 1 2 , and -14 -1 4 . Following the obove properties, the ROC is |z|>12 z 1 2 .

### Example 2

Now take

x 2 n=-14nun12nu(n)1 x 2 n -1 4 n u n 1 2 n u n 1
(13)
The z-transform and ROC of -14nun -1 4 n u n was shown in the example above. The z-transorm of (12n)u(n)1 1 2 n u n 1 is zz12 z z 1 2 with an ROC at |z|>12 z 1 2 .

Once again, by linearity,

X 2 z=zz+14+zz12=z(2z18)(z+14)(z12) X 2 z z z 1 4 z z 1 2 z 2 z 1 8 z 1 4 z 1 2
(14)
By observation it is again clear that there are two zeros, at 0 0 and 116 1 16 , and two poles, at 12 1 2 , and -14 -1 4 . in ths case though, the ROC is |z|<12 z 1 2 .

## Content actions

### Give feedback:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks


text:
Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.algorithms.sparsifiers

# Copyright (C) 2018
# Robert Gmyr <robert@gmyr.net>
"""Functions for computing sparsifiers of graphs."""
from __future__ import division
import math
import networkx as nx
from networkx.utils import not_implemented_for, py_random_state

__all__ = ['spanner']

[docs]@py_random_state(3)
@not_implemented_for('directed')
@not_implemented_for('multigraph')
def spanner(G, stretch, weight=None, seed=None):
"""Returns a spanner of the given graph with the given stretch.

A spanner of a graph G = (V, E) with stretch t is a subgraph
H = (V, E_S) such that E_S is a subset of E and the distance between
any pair of nodes in H is at most t times the distance between the
nodes in G.

Parameters
----------
G : NetworkX graph
An undirected simple graph.

stretch : float
The stretch of the spanner.

weight : object
The edge attribute to use as distance.

seed : integer, random_state, or None (default)
Indicator of random number generation state.
See :ref:Randomness<randomness>.

Returns
-------
NetworkX graph
A spanner of the given graph with the given stretch.

Raises
------
ValueError
If a stretch less than 1 is given.

Notes
-----
This function implements the spanner algorithm by Baswana and Sen,
see [1].

This algorithm is a randomized las vegas algorithm: The expected
running time is O(km) where k = (stretch + 1) // 2 and m is the
number of edges in G. The returned graph is always a spanner of the
given graph with the specified stretch. For weighted graphs the
number of edges in the spanner is O(k * n^(1 + 1 / k)) where k is
defined as above and n is the number of nodes in G. For unweighted
graphs the number of edges is O(n^(1 + 1 / k) + kn).

References
----------
[1] S. Baswana, S. Sen. A Simple and Linear Time Randomized
Algorithm for Computing Sparse Spanners in Weighted Graphs.
Random Struct. Algorithms 30(4): 532-563 (2007).
"""
if stretch < 1:
raise ValueError('stretch must be at least 1')

k = (stretch + 1) // 2

# initialize spanner H with empty edge set
H = nx.empty_graph()

# phase 1: forming the clusters
# the residual graph has V' from the paper as its node set
# and E' from the paper as its edge set
residual_graph = _setup_residual_graph(G, weight)
# clustering is a dictionary that maps nodes in a cluster to the
# cluster center
clustering = {v: v for v in G.nodes}
sample_prob = math.pow(G.number_of_nodes(), - 1 / k)
size_limit = 2 * math.pow(G.number_of_nodes(), 1 + 1 / k)

i = 0
while i < k - 1:
# step 1: sample centers
sampled_centers = set()
for center in set(clustering.values()):
if seed.random() < sample_prob:

# combined loop for steps 2 and 3
edges_to_remove = set()
new_clustering = {}
for v in residual_graph.nodes:
if clustering[v] in sampled_centers:
continue

# step 2: find neighboring (sampled) clusters and
# lightest edges to them
lightest_edge_neighbor, lightest_edge_weight =\
_lightest_edge_dicts(residual_graph, clustering, v)
neighboring_sampled_centers =\
set(lightest_edge_weight.keys()) & sampled_centers

# step 3: add edges to spanner
if not neighboring_sampled_centers:
# connect to each neighboring center via lightest edge
for neighbor in lightest_edge_neighbor.values():
# remove all incident edges

else:  # there is a neighboring sampled center
closest_center = min(neighboring_sampled_centers,
key=lightest_edge_weight.get)
closest_center_weight = lightest_edge_weight[closest_center]
closest_center_neighbor =\
lightest_edge_neighbor[closest_center]

new_clustering[v] = closest_center

# connect to centers with edge weight less than
# closest_center_weight
for center, edge_weight in lightest_edge_weight.items():
if edge_weight < closest_center_weight:
neighbor = lightest_edge_neighbor[center]

# remove edges to centers with edge weight less than
# closest_center_weight
neighbor_cluster = clustering[neighbor]
neighbor_weight = lightest_edge_weight[neighbor_cluster]
if neighbor_cluster == closest_center or neighbor_weight < closest_center_weight:

# check whether iteration added too many edges to spanner,
# if so repeat
# an iteration is repeated O(1) times on expectation
continue

# iteration succeeded
i = i + 1

# actually add edges to spanner

# actually delete edges from residual graph
residual_graph.remove_edges_from(edges_to_remove)

# copy old clustering data to new_clustering
for node, center in clustering.items():
if center in sampled_centers:
new_clustering[node] = center
clustering = new_clustering

# step 4: remove intra-cluster edges
for u in residual_graph.nodes:
if clustering[u] == clustering[v]:
residual_graph.remove_edge(u, v)

# update residual graph node set
for v in list(residual_graph.nodes):
if v not in clustering:
residual_graph.remove_node(v)

# phase 2: vertex-cluster joining
for v in residual_graph.nodes:
lightest_edge_neighbor, _ =\
_lightest_edge_dicts(residual_graph, clustering, v)
for neighbor in lightest_edge_neighbor.values():

return H

def _setup_residual_graph(G, weight):
"""Setup residual graph as a copy of G with unique edges weights.

The node set of the residual graph corresponds to the set V' from
the Baswana-Sen paper and the edge set corresponds to the set E'
from the paper.

This function associates distinct weights to the edges of the
residual graph (even for unweighted input graphs), as required by
the algorithm.

Parameters
----------
G : NetworkX graph
An undirected simple graph.

weight : object
The edge attribute to use as distance.

Returns
-------
NetworkX graph
The residual graph used for the Baswana-Sen algorithm.
"""
residual_graph = G.copy()

# establish unique edge weights, even for unweighted graphs
for u, v in G.edges():
if not weight:
residual_graph[u][v]['weight'] = (id(u), id(v))
else:
residual_graph[u][v]['weight'] = (G[u][v][weight], id(u), id(v))

return residual_graph

def _lightest_edge_dicts(residual_graph, clustering, node):
"""Find the lightest edge to each cluster.

Searches for the minimum-weight edge to each cluster adjacent to
the given node.

Parameters
----------
residual_graph : NetworkX graph
The residual graph used by the Baswana-Sen algorithm.

clustering : dictionary
The current clustering of the nodes.

node : node
The node from which the search originates.

Returns
-------
lightest_edge_neighbor, lightest_edge_weight : dictionary, dictionary
lightest_edge_neighbor is a dictionary that maps a center C to
a node v in the corresponding cluster such that the edge from
the given node to v is the lightest edge from the given node to
any node in cluster. lightest_edge_weight maps a center C to the
weight of the aforementioned edge.

Notes
-----
If a cluster has no node that is adjacent to the given node in the
residual graph then the center of the cluster is not a key in the
returned dictionaries.
"""
lightest_edge_neighbor = {}
lightest_edge_weight = {}
neighbor_center = clustering[neighbor]
weight = residual_graph[node][neighbor]['weight']
if neighbor_center not in lightest_edge_weight or\
weight < lightest_edge_weight[neighbor_center]:
lightest_edge_neighbor[neighbor_center] = neighbor
lightest_edge_weight[neighbor_center] = weight
return lightest_edge_neighbor, lightest_edge_weight

def _add_edge_to_spanner(H, residual_graph, u, v, weight):
"""Add the edge {u, v} to the spanner H and take weight from
the residual graph.

Parameters
----------
H : NetworkX graph
The spanner under construction.

residual_graph : NetworkX graph
The residual graph used by the Baswana-Sen algorithm. The weight
for the edge is taken from this graph.

u : node
One endpoint of the edge.

v : node
The other endpoint of the edge.

weight : object
The edge attribute to use as distance.
"""


text:
# How does a three-phase transformer work with phases sharing a common core?

Google search reveals a lot of pictures of three-phase transformers. Looks like a common setup is to have three pairs of winding and a shared core. The core typically consists of three "bars" in parallel and each pair of windings is wrapped onto its own "bar" and the "bars" are connected on both ends so the core is closed and effectively it is one single core of complex shape and each pair of windings occupies its dedicated place on the core.

-----------  << the two horizontal bars are free
|    |    |
|    |    |  << windings are wrapped onto this vertical bars
|    |    |  << each pair occupies a separate bar
|    |    |
|    |    |
-----------

Now as I see it each phase will induce its own magnetic flux and since each phase is offset by 120 degrees its flux will also be offset and those three fluxes should mix and more or less annihilate each other (full annihilation should happen when all phases are loaded equally) and so the transformer should not output any power on the secondary windings. However three-phase transformers work just fine.

How does a three-phase transformer work with magnetic flux of each phase passing through the common core?

-
Related –  Dean Feb 17 '12 at 12:49
Did you ever heard about law of conservation of energy? It is one of the basic principles of our existence. The phases cannot "annihilate" themselves when put together. –  Al Kepp Feb 17 '12 at 23:49
@Al Kepp: Actually current in the neutral wire is exactly zero when all phases are equally loaded - right because of currents summing up and "annihilating" each other. I expected fluxes to behave the same way. –  sharptooth Feb 20 '12 at 6:14
@sharptooth: In an ideal 3-phase case, current goes forward and back in those 3 phase wires. It is not "annihilated" anywhere. Fourth wire isn't used, but that's not because of "annihilation" - it's because current goes in both directions in the three phase wires and doesn't need any additional wire. –  Al Kepp Feb 20 '12 at 18:33

You are correct that in each winding, the magnetic field varies in phase with the current in the windings. What you're having a problem with is the concept of flux being 'annihilated' at where the cores are joined.

It's helpful here to think about 'magnetic circuits'. Think about a single phase transformer for a moment; the core completes a loop that passes through the windings, so the field from the windings has a closed path. Now think about a three phase transformer. Look at the phase A winding. It has a certain amount of field that needs to be returned from one end of the winding to the other. You could just close it on itself, and do the same with phases B and C, and have three separate single-phase transformers, and it would get the job done, but it would be wasteful of material. Consider that the phase relationship of the currents means that, at any given moment, the fields from phases B and C added together are equal and opposite to that of phase A. It doesn't matter which phase you look at, the fields from the other two add to cancel. You see, where you were surmising that the fields annihilated eachother, what in fact happens is that they complement one another, and provide the right amount of magnetic return path. This lets you use less core material, and so economics dictates that's the way to go.

It's a bit like what happens to the currents in a Y-connected three phase load; the currents sum to zero, but it's not that they annihilate one another, it's that they form balanced return paths for one another.

-
I like the magnetic-circuit analogy. Magnetic fields don't have associated particles the way electric currents do, but they behave somewhat as though they do: a current through a coil of wire may be thought of as pushing magnetic "stuff" (flux) out one end which then wants to go around the coil and flow back in the other; anything that impedes this flow will receive energy. At any given time, in a vertically-mounted three-phase transformer, if two coils are moving a certain amount of flux upward, the third coil will move twice as much downward, thus letting flux move... –  supercat Oct 15 '12 at 17:53
...smoothly, entirely within the transformer core. –  supercat Oct 15 '12 at 17:54

The key here is that each individual core has the primary and secondary pairs for that phase on it. While you are correct that for the transformer as a whole the fluxes should sum to zero, in each individual core you effectively only see the flux for that particular phase - the entire flux does not pass through each of those cores.

-
Then why use a closed single core instead of just three separate bars? –  sharptooth Feb 16 '12 at 13:00
@sharptooth Maybe there is a neutral winding? –  clabacchio Feb 16 '12 at 13:01
Efficiency would be my guess - closing the transformer means you aren't having to deal with losses from the flux outside the core. –  Rory Alsop Feb 16 '12 at 13:02
@sharptooth - The magnetic flux is much higher for a closed core. Think of the magnetic lines which remain concentrated in the core instead of spreading through the air. –  stevenvh Feb 18 '12 at 10:14

If the following commands are copied and pasted in MATLAB, you will have a triple phase in a period with frequency of 1.

t=0:0.000001:(2*pi); y1=220*sin(t-(pi/6));y2=220*sin((t-(pi/6))+(2*pi/3));y3=220*sin((t-(pi/6))+(4*pi/3)); plot(t,y1,t,y2,t,y3);grid on

Magnetic flux that flows in each leg of 3-phase transformer is same as three phase current waveforms. There are 6 important areas in a period because there are 3 phases which divide a period into three areas with 120 degrees, and in each area there are 2 phases that one of them is increasing and another one is decreasing and their curves will cut the other. So, every one of third is divided in two parts and we have 6 important areas. In every one of sixths; one phase core injects flux in other two phases' core or two phases core inject flux in one other phase core.

Blue Red Green

0 to pi/3 ↑ ↓ ↓ 1 phase is injecting

Pi/3 to 2pi/3 ↑ ↑ ↓ 2 phases are injecting

2pi/3 to pi ↓ ↑ ↓ 1 phase is injecting

Pi to 4pi/3 ↓ ↑ ↑ 2 phases are injecting

4pi/3 to 5pi/3 ↓ ↓ ↑ 1 phase is injecting

5pi/3 to 2pi ↑ ↓ ↑ 2 phases are injecting

But the most important thing that should not be ignored is; some fluxes are flowing into the oil of transformer and because of financial limitation it is ignored. But in power plant transformers I have seen these solutions: 1- Using 5 legs transformer core. In these transformers, there are two legs beside nearest phases and their volume is half of main legs. 2- Using shell type transformers which coils are covered with core and dispersal flux is very low. 3- Using core parts on transformer tanks that don't have any connection with the main core and make a less lose way for dispersal flux.

-
Interesting answer, but it doesn't address the original question. –  Dave Tweed Oct 15 '12 at 15:40


text:
+0

0
55
2

The quadratic $$2x^2-3x+27$$ has two imaginary roots. What is the sum of the squares of these roots? Express your answer as a decimal rounded to the nearest hundredth.

Dec 1, 2019
edited by Guest  Dec 1, 2019

#1
+1009
-1

$$x=\frac{3\pm \sqrt{9-4\times 2\times 27}}{4}$$

$$x=\frac{3+3\sqrt{23}i}{4}, \frac{3-3\sqrt{23}i}{4}$$

Square both to get

$$x^2=\frac{-198+12\sqrt 23i}{16}, \frac{-198-12\sqrt 23i}{16}$$

You are very welcome!

:P

Dec 1, 2019
#2
0

how do I do that?

Guest Dec 2, 2019


text:
+0

# HELP!!

0
102
1

For what real number $v$ is $\frac{-21-\sqrt{301}}{10}$ a solution to $5x^2+21x+v = 0$?

Feb 12, 2022


text:
## Soil Mechanics- Cohesionless Soil Nphi

Very silly question, but how do we find the angle using calculator. Its a step in a soil mech problem.

2. Relevant equations

The equation is :

Nphi= tan2(45+ θ/2)

given that Nphi= 4.183, the equation becomes

4.183= tan2(45+ θ/2)

How do we calculate this?

Edit: Sorry Mods can you please delete this thread. I figured it out :)


text:
## Elementary and Intermediate Algebra: Concepts & Applications (6th Edition)

$\text{Set Builder Notation: } \left\{ t|t\lt3 \right\} \\\text{Interval Notation: } \left( -\infty,3 \right)$
$\bf{\text{Solution Outline:}}$ Use the properties of inequality to solve the given inequality, $8-t\gt5 .$ Write the answer in both set-builder notation and interval notation. $\bf{\text{Solution Details:}}$ Using the properties of inequality, the inequality above is equivalent to \begin{array}{l}\require{cancel} 8-t\gt5 \\\\ -t\gt5-8 \\\\ -t\gt-3 .\end{array} Dividing both sides by a negative number (and consequently reversing the inequality symbol), the inequality above is equivalent to \begin{array}{l}\require{cancel} -t\gt-3 \\\\ t\lt\dfrac{-3}{-1} \\\\ t\lt3 .\end{array} Hence, the solution set is \begin{array}{l}\require{cancel} \text{Set Builder Notation: } \left\{ t|t\lt3 \right\} \\\text{Interval Notation: } \left( -\infty,3 \right) .\end{array}


text:
# Question #05209

Jan 2, 2016

The answer is (b) $\text{pH} < 7$

#### Explanation:

Hydrochloric acid, $\text{HCl}$, a strong acid, will react with ammonia, ${\text{NH}}_{3}$, a weak base, to form ammonium ions, ${\text{NH}}_{4}^{+}$ and chloride anions, ${\text{Cl}}^{-}$.

At equivalent point, both the strong acid and the weak base have been consumed by this neutralization reaction.

${\text{HCl"_text((aq]) + "NH"_text(3(aq]) -> "NH"_text(4(aq])^(+) + "Cl}}_{\textrm{\left(a q\right]}}^{-}$

The important thing to realize now is that the ammonium ion, which is the conjugate acid of ammonia, will actually react with the water molecules to reform some of the weak base and produce hydronium ions, ${\text{H"_3"O}}^{+}$

${\text{NH"_text(4(aq])^(+) + "H"_2"O"_text((aql]) rightleftharpoons "NH"_text(3(aq]) + "H"_3"O}}_{\textrm{\left(a q\right]}}^{+}$

Since the concentration of hydronium ions increases as a result of this equilibrium reaction, the pH of the solution will decrease.

This means that the titration of a strong acid with a weak base will produce a solution of $\text{pH} < 7$ at equivalence point.

Similarly, titrating a weak acid with a strong base will produce a solution of $\text{pH} > 7$ at equivalence point, since the neutralization reaction produces the conjugate base of the acid, which then reacts with water to produce hydroxide anions, ${\text{OH}}^{-}$.