Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older editNewer edit →
No edit summary
mNo edit summary
Line 1: Line 1:
In [[recreational mathematics]], a '''repunit''' is a [[number]] like 11, 111, or 1111 that contains only the digit 1 &mdash; a more specific type of [[repdigit]]. The term stands for '''rep'''eated '''unit''' and was coined in 1966 by [[Albert H. Beiler]] in his book ''Recreations in the Theory of Numbers''.<ref>{{cite book|last1=Beiler|first1=Albert|title=Recreations in the Theory of Numbers: The Queen of Mathematics Entertains|date=2013|publisher=Dover Publications|location=New York|isbn=978-0-486-21096-4|page=83|edition=2|accessdate=21 June 2014}}</ref><!--- Original publication was 1964; did he coin repunit in that edition? or was this added in 1966? --->
{{Infobox Algorithm
|class=[[Single-source shortest path problem]] (for weighted directed graphs)
|image=
|caption =  
|data=[[Graph (data structure)|Graph]]
|time=<math>O (|V| |E|)</math>
|space=<math>O (|V|)</math>
}}


A '''repunit prime''' is a repunit that is also a [[prime number]]. Primes that are repunits in [[Binary number|base 2]] are [[Mersenne prime]]s.
{{Tree search algorithm}}


== Definition ==
The '''Bellman–Ford algorithm''' computes single-source [[shortest path]]s in a [[weighted digraph]].<ref name="Bang">{{Cite book|first=Jørgen |last=Bang-Jensen||coauthors=Gregory Gutin|title=Digraphs: Theory, Algorithms and Applications|edition=First |isbn=978-1-84800-997-4|chapter=Section 2.3.4: The Bellman-Ford-Moore algorithm|url=http://www.cs.rhul.ac.uk/books/dbook/}}</ref>
For graphs with only non-negative edge weights, the faster [[Dijkstra's algorithm]] also solves the problem.
Thus, Bellman–Ford is used primarily for graphs with negative edge weights.
The algorithm is named after its developers, [[Richard Bellman]] and [[L. R. Ford, Jr.|Lester Ford, Jr.]]


The base-''b'' repunits are defined as (this ''b'' can be either positive or negative)
Negative edge weights are found in various applications of graphs, hence the usefulness of this algorithm.<ref>{{Cite book|first=Robert |last=Sedgewick|title= Algorithms in Java|edition= Third |isbn= 0-201-36121-3|chapter=Section 21.7: Negative Edge Weights|url=http://safari.oreilly.com/0201361213/ch21lev1sec7|ref=harv|postscript=<!-- Bot inserted parameter. Either remove it; or change its value to "." for the cite to end in a ".", as necessary. -->{{inconsistent citations}}}}</ref>
:<math>R_n^{(b)}={b^n-1\over{b-1}}\qquad\mbox{for }|b|\ge2, n\ge1.</math>
However, if a graph contains a "negative cycle", i.e., a [[cycle (graph theory)|cycle]] whose edges sum to a negative value, then [[Walk (graph theory)|walks]] of arbitrarily low weight can be constructed by repeatedly following the cycle, so there may not be a ''shortest'' path.
Thus, the number ''R''<sub>''n''</sub><sup>''(b)''</sup> consists of ''n'' copies of the digit 1 in base b representation. The first two repunits base ''b'' for ''n''=1 and ''n''=2 are
In such a case, the Bellman-Ford algorithm can detect negative cycles and report their existence, but it cannot produce a correct "shortest path" answer if a negative cycle is reachable from the source.<ref>Kleinberg, Jon; Tardos, Éva (2006), Algorithm Design, New York: Pearson Education, Inc..</ref><ref name="Bang"/>
:<math>R_1^{(b)}={b-1\over{b-1}}= 1 \qquad \text{and} \qquad R_2^{(b)}={b^2-1\over{b-1}}= b+1\qquad\text{for}\ |b|\ge2.</math>


In particular, the ''[[decimal]] (base-10) repunits'' that are often referred to as simply ''repunits'' are defined as
==Algorithm==
:<math>R_n=R_n^{(10)}={10^n-1\over{10-1}}={10^n-1\over9}\qquad\mbox{for }n\ge1.</math>
Bellman–Ford is based on [[dynamic programming]] approach. In its basic structure it is similar to [[Dijkstra's Algorithm]], but instead of [[Greedy algorithm|greedily]] selecting the minimum-weight node not yet processed to relax, it simply relaxes ''all'' the edges, and does this |''V'' |&nbsp;&minus;&nbsp;1 times, where |''V'' | is the number of vertices in the graph. The repetitions allow minimum distances to propagate accurately throughout the graph, since, in the absence of negative cycles, the shortest path can visit each node at most only once. Unlike the greedy approach, which depends on certain structural assumptions derived from positive weights, this straightforward approach extends to the general case.
Thus, the number ''R''<sub>''n''</sub> = ''R''<sub>''n''</sub><sup>''(10)''</sup> consists of ''n'' copies of the digit 1 in base 10 representation. The sequence of repunits base 10 starts with
: [[1 (number)|1]], [[11 (number)|11]], [[111 (number)|111]], 1111, 11111, 111111, ... {{OEIS|A002275}}.


Similarly, the repunits [[base 2]] are defined as
Bellman–Ford runs in ''[[Big O notation|O]]''(|''V''|·|''E''|) time, where |''V''| and |''E''| are the number of vertices and edges respectively.
:<math>R_n^{(2)}={2^n-1\over{2-1}}={2^n-1}\qquad\mbox{for }n\ge1.</math>
Thus, the number ''R''<sub>''n''</sub><sup>''(2)''</sup> consists of ''n'' copies of the digit 1 in base 2 representation. In fact, the base-2 repunits are the well-known [[Mersenne prime|Mersenne number]]s ''M''<sub>''n''</sub>&nbsp;=&nbsp;2<sup>''n''</sup>&nbsp;&minus;&nbsp;1, they start with
:1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, ... {{OEIS|id=A000225}}


== Properties ==
  '''procedure''' BellmanFord(''list'' vertices, ''list'' edges, ''vertex'' source)
* Any repunit in any base having a composite number of digits is necessarily composite.  Only repunits (in any base) having a prime number of digits might be prime. This is a necessary but not sufficient condition.  For example,
    ''// This implementation takes in a graph, represented as lists of vertices''
*: ''R''<sub>35</sub><sup>(''b'')</sup> = {{repeat|1|35}} = 11111 × 1000010000100001000010000100001 = 1111111 × 10000001000000100000010000001,
    ''// and edges, and modifies the vertices so that their ''distance'' and''
:since 35 = 7 × 5 = 5 × 7. This repunit factorization does not depend on the base ''b'' in which the repunit is expressed.
    ''//'' predecessor ''attributes store the shortest paths.''
* Any positive multiple of the repunit ''R''<sub>''n''</sub><sup>(''b'')</sup> contains at least ''n'' nonzero digits in base ''b''.
* The only known numbers that are repunits with at least 3 digits in more than one base simultaneously are 31 (111 in base 5, 11111 in base 2) and 8191 (111 in base 90, 1111111111111 in base 2). The [[Goormaghtigh conjecture]] says there are only these two cases.
    ''// Step 1: initialize graph''
* Using the [[pigeon-hole principle]] it can be easily shown that for each ''n'' and ''b'' such that ''n''  and ''b'' are [[relative prime|relatively prime]] there exists a repunit in base ''b'' that is a multiple of ''n''. To see this consider repunits ''R''<sub>1</sub><sup>(''b'')</sup>,...,''R''<sub>''n''</sub><sup>(''b'')</sup>. Assume none of the ''R''<sub>''k''</sub><sup>(''b'')</sup> is divisible by ''n''. Because there are ''n'' repunits but only ''n''-1 non-zero residues modulo ''n'' there exist two repunits ''R''<sub>''i''</sub><sup>(''b'')</sup> and ''R''<sub>''j''</sub><sup>(''b'')</sup> with 1≤''i''<''j''≤''n'' such that ''R''<sub>''i''</sub><sup>(''b'')</sup> and ''R''<sub>''j''</sub><sup>(''b'')</sup> have the same residue modulo ''n''. It follows that ''R''<sub>''j''</sub><sup>(''b'')</sup> - ''R''<sub>''i''</sub><sup>(''b'')</sup> has residue 0 modulo ''n'', i.e. is divisible by ''n''. ''R''<sub>''j''</sub><sup>(''b'')</sup> - ''R''<sub>''i''</sub><sup>(''b'')</sup> consists of ''j'' - ''i'' ones followed by ''i'' zeroes. Thus, ''R''<sub>''j''</sub><sup>(''b'')</sup> - ''R''<sub>''i''</sub><sup>(''b'')</sup> = ''R''<sub>''j''-''i''</sub><sup>(''b'')</sup>  x ''b''<sup>''i''</sup> . Since ''n'' divides the left-hand side it also divides the right-hand side and since ''n'' and ''b'' are relative prime ''n'' must divide ''R''<sub>''j''-''i''</sub><sup>(''b'')</sup> [[proof by contradiction|contradicting]] the original assumption.
    '''for each''' vertex v '''in''' vertices:
* The [[Feit–Thompson conjecture]] is that ''R''<sub>''q''</sub><sup>(''p'')</sup> never divides ''R''<sub>''p''</sub><sup>(''q'')</sup> for two distinct primes ''p'' and ''q''.
        '''if''' v '''is''' source '''then''' v.distance := 0
        '''else''' v.distance := '''infinity'''
        v.predecessor := '''null'''
    ''// Step 2: relax edges repeatedly''
    '''for''' i '''from''' 1 '''to''' size(vertices)-1:
        '''for each''' edge uv '''in''' edges: ''// uv is the edge from u to v''
            u := uv.source
            v := uv.destination
            '''if''' u.distance + uv.weight < v.distance:
                v.distance := u.distance + uv.weight
                v.predecessor := u
    ''// Step 3: check for negative-weight cycles''
    '''for each''' edge uv '''in''' edges:
        u := uv.source
        v := uv.destination
        '''if''' u.distance + uv.weight < v.distance:
            '''error''' "Graph contains a negative-weight cycle"


== Factorization of decimal repunits ==
==Proof of correctness==


(Prime factors colored {{color|red|red}} means "new factors", the prime factor divides ''R''<sub>''n''</sub> but not divides ''R''<sub>''k''</sub> for all ''k'' < ''n'') {{OEIS|id=A102380}}
The correctness of the algorithm can be shown by [[mathematical induction|induction]]. The precise statement shown by induction is:


{|
'''Lemma'''. After ''i'' repetitions of ''for'' cycle:
|-
* If Distance(''u'') is not infinity, it is equal to the length of some path from ''s'' to ''u'';
||
* If there is a path from ''s'' to ''u'' with at most ''i'' edges, then Distance(u) is at most the length of the shortest path from ''s'' to ''u'' with at most ''i'' edges.
{|
|-
|''R''<sub>1</sub> =||1
|-
|''R''<sub>2</sub> =||{{color|red|11}}
|-
|''R''<sub>3</sub> =||{{color|red|3}} · {{color|red|37}}
|-
|''R''<sub>4</sub> =||11 · {{color|red|101}}
|-
|''R''<sub>5</sub> =||{{color|red|41}} · {{color|red|271}}
|-
|''R''<sub>6</sub> =||3 · {{color|red|7}} · 11 · {{color|red|13}} · 37
|-
|''R''<sub>7</sub> =||{{color|red|239}} · {{color|red|4649}}
|-
|''R''<sub>8</sub> =||11 · {{color|red|73}} · 101 · {{color|red|137}}
|-
|''R''<sub>9</sub> =||3<sup>2</sup> · 37 · {{color|red|333667}}
|-
|''R''<sub>10</sub> =||11 · 41 · 271 · {{color|red|9091}}
|}
||
{|
|-
|''R''<sub>11</sub> =||{{color|red|21649}} · {{color|red|513239}}
|-
|''R''<sub>12</sub> =||3 · 7 · 11 · 13 · 37 · 101 · {{color|red|9901}}
|-
|''R''<sub>13</sub> =||{{color|red|53}} · {{color|red|79}} · {{color|red|265371653}}
|-
|''R''<sub>14</sub> =||11 · 239 · 4649 · {{color|red|909091}}
|-
|''R''<sub>15</sub> =||3 · {{color|red|31}} · 37 · 41 · 271 · {{color|red|2906161}}
|-
|''R''<sub>16</sub> =||11 · {{color|red|17}} · 73 · 101 · 137 · {{color|red|5882353}}
|-
|''R''<sub>17</sub> =||{{color|red|2071723}} · {{color|red|5363222357}}
|-
|''R''<sub>18</sub> =||3<sup>2</sup> · 7 · 11 · 13 · {{color|red|19}} · 37 · {{color|red|52579}} · 333667
|-
|''R''<sub>19</sub> =||{{color|red|{{repeat|1|19}}}}
|-
|''R''<sub>20</sub> =||11 · 41 · 101 · 271 · {{color|red|3541}} · 9091 · {{color|red|27961}}
|}
||
{|
|-
|''R''<sub>21</sub> =||3 · 37 · {{color|red|43}} · 239 · {{color|red|1933}} · 4649 · {{color|red|10838689}}
|-
|''R''<sub>22</sub> =||11<sup>2</sup> · {{color|red|23}} · {{color|red|4093}} · {{color|red|8779}} · 21649 · 513239
|-
|''R''<sub>23</sub> =||{{color|red|{{repeat|1|23}}}}
|-
|''R''<sub>24</sub> =||3 · 7 · 11 · 13 · 37 · 73 · 101 · 137 · 9901 · {{color|red|99990001}}
|-
|''R''<sub>25</sub> =||41 · 271 · {{color|red|21401}} · {{color|red|25601}} · {{color|red|182521213001}}
|-
|''R''<sub>26</sub> =||11 · 53 · 79 · {{color|red|859}} · 265371653 · {{color|red|1058313049}}
|-
|''R''<sub>27</sub> =||3<sup>3</sup> · 37 · {{color|red|757}} · 333667 · {{color|red|440334654777631}}
|-
|''R''<sub>28</sub> =||11 · {{color|red|29}} · 101 · 239 · {{color|red|281}} · 4649 · 909091 · {{color|red|121499449}}
|-
|''R''<sub>29</sub> =||{{color|red|3191}} · {{color|red|16763}} · {{color|red|43037}} · {{color|red|62003}} · {{color|red|77843839397}}
|-
|''R''<sub>30</sub> =||3 · 7 · 11 · 13 · 31 · 37 · 41 · {{color|red|211}} · {{color|red|241}} · 271 · {{color|red|2161}} · 9091 · 2906161
|}
|}


Smallest prime factor of ''R''<sub>''n''</sub> are
'''Proof'''. For the base case of induction, consider <code>i=0</code> and the moment before ''for'' cycle is executed for the first time. Then, for the source vertex, <code>source.distance = 0</code>, which is correct. For other vertices ''u'', <code>u.distance = '''infinity'''</code>, which is also correct because there is no path from ''source'' to ''u'' with 0 edges.
:1, 11, 3, 11, 41, 3, 239, 11, 3, 11, 21649, 3, 53, 11, 3, 11, 2071723, 3, 1111111111111111111, 11, 3, 11, 11111111111111111111111, 3, 41, 11, 3, 11, 3191, 3, 2791, 11, 3, 11, 41, 3, 2028119, 11, 3, 11, 83, 3, 173, 11, 3, 11, 35121409, 3, 239, 11, ... {{OEIS|id=A067063}}


==Repunit primes==
For the inductive case, we first prove the first part. Consider a moment when a vertex's distance is updated by
The definition of repunits was motivated by recreational mathematicians looking for [[integer factorization|prime factors]] of such numbers.
<code>v.distance := u.distance + uv.weight</code>. By inductive assumption, <code>u.distance</code> is the length of some path from ''source'' to ''u''. Then <code>u.distance + uv.weight</code> is the length of the path from ''source'' to ''v'' that follows the path from  ''source'' to ''u'' and then goes to ''v''.


It is easy to show that if ''n'' is divisible by ''a'', then ''R''<sub>''n''</sub><sup>(''b'')</sup> is divisible by ''R''<sub>''a''</sub><sup>(''b'')</sup>:
For the second part, consider the shortest path from ''source'' to ''u'' with at most ''i'' edges. Let ''v'' be the last vertex before ''u'' on this path. Then, the part of the path from ''source'' to ''v'' is the shortest path from ''source'' to ''v'' with at most ''i-1'' edges. By inductive assumption, <code>v.distance</code> after ''i''−1 cycles is at most the length of this path. Therefore, <code>uv.weight + v.distance</code> is at most the length of the path from ''s'' to ''u''. In the ''i<sup>th</sup>'' cycle, <code>u.distance</code> gets compared with <code>uv.weight + v.distance</code>, and is set equal to it if <code>uv.weight + v.distance</code> was smaller. Therefore, after ''i'' cycles, <code>u.distance</code> is at most the length of the shortest path from ''source'' to ''u'' that uses at most ''i'' edges.


:<math>R_n^{(b)}=\frac{1}{b-1}\prod_{d|n}\Phi_d(b)</math>
If there are no negative-weight cycles, then every shortest path visits each vertex at most once, so at step 3 no further improvements can be made. Conversely, suppose no improvement can be made. Then for any cycle with vertices ''v''[0], ..., ''v''[''k''−1],


where <math>\Phi_d(x)</math> is the <math>d^\mathrm{th}</math> [[cyclotomic polynomial]] and ''d'' ranges over the divisors of ''n''. For ''p'' prime, <math>\Phi_p(x)=\sum_{i=0}^{p-1}x^i</math>, which has the expected form of a repunit when ''x'' is substituted with ''b''.
<code>v[i].distance <= v[(i-1) mod k].distance + v[(i-1) mod k]v[i].weight</code>


For example, 9 is divisible by 3, and thus ''R''<sub>9</sub> is divisible by ''R''<sub>3</sub>&mdash;in fact, 111111111&nbsp;=&nbsp;111&nbsp;·&nbsp;1001001. The corresponding cyclotomic polynomials <math>\Phi_3(x)</math> and <math>\Phi_9(x)</math> are <math>x^2+x+1</math> and <math>x^6+x^3+1</math> respectively. Thus, for ''R''<sub>''n''</sub> to be prime ''n'' must necessarily be prime.
Summing around the cycle, the ''v''[''i''].distance terms and the ''v''[''i''−1 (mod ''k'')] distance terms cancel, leaving
But it is not sufficient for ''n'' to be prime; for example, ''R''<sub>3</sub>&nbsp;=&nbsp;111&nbsp;=&nbsp;3&nbsp;·&nbsp;37 is not prime. Except for this case of ''R''<sub>3</sub>, ''p'' can only divide ''R''<sub>''n''</sub> for prime ''n'' if ''p = 2kn + 1'' for some ''k''.


=== Decimal repunit primes ===
<code>0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight</code>
''R''<sub>''n''</sub> is prime for ''n''&nbsp;=&nbsp;2,&nbsp;19,&nbsp;23, 317, 1031, ... (sequence [[OEIS:A004023|A004023]] in [[OEIS]]). ''R''<sub>49081</sub> and ''R''<sub>86453</sub> are [[probable prime|probably prime]].  On April 3, 2007 [[Harvey Dubner]] (who also found ''R''<sub>49081</sub>) announced that ''R''<sub>109297</sub> is a probable prime.<ref>Harvey Dubner, ''[http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0704&L=nmbrthry&T=0&P=178 New Repunit R(109297)]''</ref> He later announced there are no others from ''R''<sub>86453</sub> to ''R''<sub>200000</sub>.<ref>Harvey Dubner, ''[http://tech.groups.yahoo.com/group/primeform/message/8546 Repunit search limit]''</ref> On July 15, 2007 Maksym Voznyy announced ''R''<sub>270343</sub> to be probably prime,<ref>Maksym Voznyy, ''[https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0707&L=NMBRTHRY&P=5903 New PRP Repunit R(270343)]''</ref> along with his intent to search to 400000. As of November 2012, all further candidates up to ''R''<sub>2500000</sub> have been tested, but no new probable primes have been found so far.


It has been conjectured that there are infinitely many repunit primes<ref>Chris Caldwell, "[http://primes.utm.edu/glossary/page.php?sort=Repunit The Prime Glossary: repunit]" at The [[Prime Pages]].</ref> and they seem to occur roughly as often as the [[prime number theorem]] would predict: the exponent of the ''N''th repunit prime is generally around a fixed multiple of the exponent of the (''N''-1)th.
I.e., every cycle has nonnegative weight.


The prime repunits are a trivial subset of the [[permutable prime]]s, i.e., primes that remain prime after any [[permutation]] of their digits.
==Finding negative cycles==
When the algorithm is used to find shortest paths, the existence of negative cycles is a problem, preventing the algorithm from finding a correct answer. However, since it terminates upon finding a negative cycle, the Bellman-Ford algorithm can be used for applications in which this is the target to be sought - for example in [[cycle-cancelling]] techniques in [[Flow network|network flow]] analysis.<ref name="Bang"/>


=== Base 2 repunit primes ===
== Applications in routing ==
{{main|Mersenne prime}}


Base 2 repunit primes are called [[Mersenne prime]]s.
A distributed variant of the Bellman–Ford algorithm is used in [[distance-vector routing protocol]]s, for example the [[Routing Information Protocol]] (RIP). The algorithm is distributed because it involves a number of nodes (routers) within an [[autonomous system (Internet)|Autonomous system]], a collection of IP networks typically owned by an ISP.
It consists of the following steps:


=== Base 3 repunit primes ===
# Each node calculates the distances between itself and all other nodes within the AS and stores this information as a table.
The first few base 3 repunit primes are
# Each node sends its table to all neighboring nodes.
: 13, 1093, 797161, 3754733257489862401973357979128773, 6957596529882152968992225251835887181478451547013 {{OEIS|A076481}}
# When a node receives distance tables from its neighbors, it calculates the shortest routes to all other nodes and updates its own table to reflect any changes.
corresponding to <math>n</math> of
: 3, 7, 13, 71, 103, 541, 1091, 1367, 1627, 4177, 9011, 9551, ... {{OEIS|A028491}}.


=== Base 4 repunit primes ===
The main disadvantages of the Bellman–Ford algorithm in this setting are as follows:
The only base 4 repunit prime is 5 (<math>11_4</math>). <math>4^n-1=\left(2^n+1\right)\left(2^n-1\right)</math>, and 3 always divides <math>2^n+1</math> when ''n'' is odd and <math>2^n-1</math> when ''n'' is even. For ''n'' greater than 2, both <math>2^n+1</math> and <math>2^n-1</math> are greater than 3, so removing the factor of 3 still leaves two factors greater than 1, so the number cannot be prime.


===Base 5 repunit primes===
* It does not scale well.
The first few base 5 repunit primes are
* Changes in [[network topology]] are not reflected quickly since updates are spread node-by-node.
: 31, 19531, 12207031, 305175781, 177635683940025046467781066894531, 14693679385278593849609206715278070972733319459651094018859396328480215743184089660644531, 35032461608120426773093239582247903282006548546912894293926707097244777067146515037165954709053039550781, 815663058499815565838786763657068444462645532258620818469829556933715405574685778402862015856733535201783524826169013977050781 {{OEIS|A086122}}
* [[Count to infinity#Count-to-infinity problem|Count to infinity]] (if link or node failures render a node unreachable from some set of other nodes, those nodes may spend forever gradually increasing their estimates of the distance to it, and in the meantime there may be routing loops).
corresponding to <math>n</math> of
: 3, 7, 11, 13, 47, 127, 149, 181, 619, 929, 3407, ... {{OEIS|A004061}}.


===Base 6 repunit primes===
==Yen's improvement==
The first few base 6 repunit primes are
{{harvtxt|Yen|1970}} described an improvement to the Bellman–Ford algorithm for a graph without negative-weight cycles. Yen's improvement first assigns some arbitrary linear order on all vertices and then partitions the set of all edges into one of two subsets. The first subset, ''E<sub>f</sub>'', contains all edges (''v<sub>i</sub>'', ''v<sub>j</sub>'') such that ''i'' < ''j''; the second, ''E<sub>b</sub>'', contains edges (''v<sub>i</sub>'', ''v<sub>j</sub>'') such that ''i'' > ''j''. Each vertex is visited in the order ''v<sub>1</sub>'', ''v<sub>2</sub>'', ..., ''v''<sub>|''V''|</sub>, relaxing each outgoing edge from that vertex in ''E<sub>f</sub>''. Each vertex is then visited in the order ''v''<sub>|''V''|</sub>, ''v''<sub>|''V''|−1</sub>, ..., ''v''<sub>1</sub>, relaxing each outgoing edge from that vertex in ''E<sub>b</sub>''. Yen's improvement effectively halves the number of "passes" required for the single-source-shortest-path solution.
: 7, 43, 55987, 7369130657357778596659, 3546245297457217493590449191748546458005595187661976371, 133733063818254349335501779590081460423013416258060407531857720755181857441961908284738707408499507 {{OEIS|A165210}}
corresponding to <math>n</math> of
: 2, 3, 7, 29, 71, 127, 271, 509, 1049, 6389, 6883, ... {{OEIS|A004062}}


===Base 7 repunit primes===
==Notes==
The first few base 7 repunit primes are
{{Reflist}}
: 2801, 16148168401, 85053461164796801949539541639542805770666392330682673302530819774105141531698707146930307290253537320447270457,<br/>138502212710103408700774381033135503926663324993317631729227790657325163310341833227775945426052637092067324133850503035623601
corresponding to <math>n</math> of
: 5, 13, 131, 149, 1699, ... {{OEIS|A004063}}
 
===Base 8 and 9 repunit primes===
The only base 8 ''or'' base 9 repunit prime is [[73 (number)|73]] (<math>111_8</math>).  <math>8^n-1=\left(4^n+2^n+1\right)\left(2^n-1\right)</math>, and 7 divides <math>4^n+2^n+1</math> when ''n'' is not divisible by 3 and <math>2^n-1</math> when ''n'' is a multiple of 3. <math>9^n-1=\left(3^n+1\right)\left(3^n-1\right)</math>, and 2 always divides both <math>3^n+1</math> and <math>3^n-1</math>.
 
===Base 12 repunit primes===
The first few base 12 repunit primes are
: 13, 157, 22621, 29043636306420266077, 435700623537534460534556100566709740005056966111842089407838902783209959981593077811330507328327968191581, 388475052482842970801320278964160171426121951256610654799120070705613530182445862582590623785872890159937874339918941
corresponding to <math>n</math> of
: 2, 3, 5, 19, 97, 109, 317, 353, 701, 9739, ... {{OEIS|A004064}}
 
===Base 20 repunit primes===
The first few base 20 repunit primes are
: 421, 10778947368421, 689852631578947368421
corresponding to <math>n</math> of
: 3, 11, 17, 1487, ... {{OEIS|A127995}}
 
===The smallest repunit prime (''p''>2) of any natural number base ''b''===
 
The list is about all bases up to 300. {{OEIS|id=A128164}}
 
{| class="wikitable"
|'''Base'''
|'''+1'''
|'''+2'''
|'''+3'''
|'''+4'''
|'''+5'''
|'''+6'''
|'''+7'''
|'''+8'''
|'''+9'''
|'''+10'''
|'''+11'''
|'''+12'''
|'''+13'''
|'''+14'''
|'''+15'''
|'''+16'''
|'''+17'''
|'''+18'''
|'''+19'''
|'''+20'''
|-
|'''0+'''
|3
|3
|3
|None
|3
|3
|5
|3
|None
|19
|17
|3
|5
|3
|3
|None
|3
|25667
|19
|3
|-
|'''20+'''
|3
|5
|5
|3
|None
|7
|3
|5
|5
|5
|7
|None
|3
|13
|313
|None
|13
|3
|349
|5
|-
|'''40+'''
|3
|1319
|5
|5
|19
|7
|127
|19
|None
|3
|4229
|103
|11
|3
|17
|7
|3
|41
|3
|7
|-
|'''60+'''
|7
|3
|5
|None
|19
|3
|19
|5
|3
|29
|3
|7
|5
|5
|3
|41
|3
|3
|5
|3
|-
|'''80+'''
|None
|23
|5
|17
|5
|11
|7
|61
|3
|3
|4421
|439
|7
|5
|7
|3343
|17
|13
|3
|None
|-
|'''100+'''
|3
|59
|19
|97
|3
|149
|17
|449
|17
|3
|3
|79
|23
|29
|7
|59
|3
|5
|3
|5
|-
|'''120+'''
|None
|5
|43
|599
|None
|7
|5
|7
|5
|37
|3
|47
|13
|5
|1171
|227
|11
|3
|163
|79
|-
|'''140+'''
|3
|1231
|3
|None
|5
|7
|3
|1201
|7
|3
|13
|&#62;10000
|3
|5
|3
|7
|17
|7
|13
|7
|-
|'''160+'''
|3
|3
|7
|3
|5
|137
|3
|3
|None
|17
|181
|5
|3
|3251
|5
|3
|5
|347
|19
|7
|-
|'''180+'''
|17
|167
|223
|&#62;10000
|&#62;10000
|7
|37
|3
|3
|13
|17
|3
|5
|3
|11
|None
|31
|5
|577
|&#62;10000
|-
|'''200+'''
|271
|37
|3
|5
|19
|3
|13
|5
|3
|&#62;10000
|41
|11
|137
|191
|3
|None
|281
|3
|13
|7
|-
|'''220+'''
|7
|5
|239
|11
|None
|127
|5
|461
|11
|5333
|3
|953
|113
|61
|7
|3
|7
|7
|5
|109
|-
|'''240+'''
|17
|19
|None
|3331
|3
|3
|17
|41
|5
|127
|7
|541
|19
|5
|5
|None
|23
|11
|2011
|5
|-
|'''260+'''
|31
|197
|5
|7
|5
|3
|13
|11
|&#62;10000
|241
|41
|3
|37
|5
|5
|31
|5
|3
|3
|7
|-
|'''280+'''
|&#62;10000
|7
|29
|2473
|5
|13
|3
|3
|None
|3
|13
|5
|3
|7
|17
|41
|17
|53
|113
|7
|}
 
There are only [[probable prime]]s for that ''b'' = 18, 51, 91, 96, 174, 230, 244, 259, and 284.
 
No known repunit primes or PRPs for that ''b'' = 152, 184, 185, 200, 210, 269, and 281.
 
Because of the algebra factorization, there are no repunit primes for that ''b'' = 4, 9, 16, 25, 32, 36, 49, 64, 81, 100, 121, 125, 144, 169, 196, 216, 225, 243, 256, and 289. {{OEIS|id=A126589}}
 
It is expected that all odd primes are in the list.
 
For [[negative base]]s (up to −300), see [[Wagstaff prime#Generalizations|Wagstaff prime]].
 
===The smallest natural number base ''b'' that <math>R_p</math> is prime for prime ''p''===
 
The list is about the first 100 primes. {{OEIS|id=A066180}}
 
{|class="wikitable"
|''p''
|2
|3
|5
|7
|11
|13
|17
|19
|23
|29
|31
|37
|41
|43
|47
|53
|59
|61
|67
|71
|-
|min ''b''
|2
|2
|2
|2
|5
|2
|2
|2
|10
|6
|2
|61
|14
|15
|5
|24
|19
|2
|46
|3
|-
|''p''
|73
|79
|83
|89
|97
|101
|103
|107
|109
|113
|127
|131
|137
|139
|149
|151
|157
|163
|167
|173
|-
|min ''b''
|11
|22
|41
|2
|12
|22
|3
|2
|12
|86
|2
|7
|13
|11
|5
|29
|56
|30
|44
|60
|-
|''p''
|179
|181
|191
|193
|197
|199
|211
|223
|227
|229
|233
|239
|241
|251
|257
|263
|269
|271
|277
|281
|-
|min ''b''
|304
|5
|74
|118
|33
|156
|46
|183
|72
|606
|602
|223
|115
|37
|52
|104
|41
|6
|338
|217
|-
|''p''
|283
|293
|307
|311
|313
|317
|331
|337
|347
|349
|353
|359
|367
|373
|379
|383
|389
|397
|401
|409
|-
|min ''b''
|13
|136
|220
|162
|35
|10
|218
|19
|26
|39
|12
|22
|67
|120
|195
|48
|54
|463
|38
|41
|-
|''p''
|419
|421
|431
|433
|439
|443
|449
|457
|461
|463
|467
|479
|487
|491
|499
|503
|509
|521
|523
|541
|-
|min ''b''
|17
|808
|404
|46
|76
|793
|38
|28
|215
|37
|236
|59
|15
|514
|260
|498
|6
|2
|95
|3
|}
 
The values of ''b'' that are [[perfect power]]s do not appear in this list, because they cannot be the base of a generalized repunit prime.<ref>{{citation
| last = Dubner | first = Harvey
| doi = 10.2307/2153263
| issue = 204
| journal = Mathematics of Computation
| mr = 1185243
| pages = 927–930
| title = Generalized repunit primes
| volume = 61
| year = 1993}}.</ref>
 
===List of repunit primes base ''b''===
{|class="wikitable"
|''b''
|''n'' which <math>R_n(b)</math> is prime (some large terms are only PRP, these ''n'''s are checked up to 100000)
|OEIS sequence
|-
|−30
|2, 139, 173, 547, 829, 2087, 2719, 3109, 10159, 56543, 80599, ...
|{{OEIS link|id=A071382}}
|-
|−29
|7, ...
|
|-
|−28
|3, 19, 373, 419, 491, 1031, 83497, ...
|{{OEIS link|id=A071381}}
|-
|−27
|None (Algebra)
|
|-
|−26
|11, 109, 227, 277, 347, 857, 2297, 9043, ...
|{{OEIS link|id=A071380}}
|-
|−25
|3, 7, 23, 29, 59, 1249, 1709, 1823, 1931, 3433, 8863, 43201, 78707, ...
|{{OEIS link|id=A057191}}
|-
|−24
|2, 7, 11, 19, 2207, 2477, 4951, ...
|{{OEIS link|id=A057190}}
|-
|−23
|11, 13, 67, 109, 331, 587, 24071, 29881, 44053, ...
|{{OEIS link|id=A057189}}
|-
|−22
|3, 5, 13, 43, 79, 101, 107, 227, 353, 7393, 50287, ...
|{{OEIS link|id=A057188}}
|-
|−21
|3, 5, 7, 13, 37, 347, 17597, 59183, 80761, 210599, ...
|{{OEIS link|id=A057187}}
|-
|−20
|2, 5, 79, 89, 709, 797, 1163, 6971, 140053, 177967, ...
|{{OEIS link|id=A057186}}
|-
|−19
|17, 37, 157, 163, 631, 7351, 26183, 30713, 41201, 77951, ...
|{{OEIS link|id=A057185}}
|-
|−18
|2, 3, 7, 23, 73, 733, 941, 1097, 1933, 4651, 481147, ...
|{{OEIS link|id=A057184}}
|-
|−17
|7, 17, 23, 47, 967, 6653, 8297, 41221, 113621, 233689, 348259, ...
|{{OEIS link|id=A057183}}
|-
|−16
|3, 5, 7, 23, 37, 89, 149, 173, 251, 307, 317, 30197, 1025393, ...
|{{OEIS link|id=A057182}}
|-
|−15
|3, 7, 29, 1091, 2423, 54449, 67489, 551927, ...
|{{OEIS link|id=A057181}}
|-
|−14
|2, 7, 53, 503, 1229, 22637, 1091401, ...
|{{OEIS link|id=A057180}}
|-
|−13
|3, 11, 17, 19, 919, 1151, 2791, 9323, 56333, ...
|{{OEIS link|id=A057179}}
|-
|−12
|2, 5, 11, 109, 193, 1483, 11353, 21419, 21911, 24071, 106859, 139739, ...
|{{OEIS link|id=A057178}}
|-
|−11
|5, 7, 179, 229, 439, 557, 6113, 223999, 327001, ...
|{{OEIS link|id=A057177}}
|-
|−10
|5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ...
|{{OEIS link|id=A001562}}
|-
|−9
|3, 59, 223, 547, 773, 1009, 1823, 3803, 49223, 193247, ...
|{{OEIS link|id=A057175}}
|-
|−8
|2 (Algebra)
|
|-
|−7
|3, 17, 23, 29, 47, 61, 1619, 18251, 106187, 201653, ...
|{{OEIS link|id=A057173}}
|-
|−6
|2, 3, 11, 31, 43, 47, 59, 107, 811, 2819, 4817, 9601, 33581, 38447, 41341, 131891, 196337, ...
|{{OEIS link|id=A057172}}
|-
|−5
|5, 67, 101, 103, 229, 347, 4013, 23297, 30133, 177337, 193939, 266863, 277183, 335429, ...
|{{OEIS link|id=A057171}}
|-
|−4
|2, 3 ([[Aurifeuillean factorization]])
|
|-
|−3
|2, 3, 5, 7, 13, 23, 43, 281, 359, 487, 577, 1579, 1663, 1741, 3191, 9209, 11257, 12743, 13093, 17027, 26633, 104243, 134227, 152287, 700897, ...
|{{OEIS link|id=A007658}}
|-
|−2
|3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399, ..., 13347311, 13372531, ... (1 is not prime)
|{{OEIS link|id=A000978}}
|-
|−1
|None (1 is not prime)
|
|-
|0
|None (1 is not prime)
|
|-
|1
|2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, ... (All primes)
|{{OEIS link|id=A000040}}
|-
|2
|2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, ..., 32582657, ..., 37156667, ..., 42643801, ..., 43112609, ..., 57885161, ...
|{{OEIS link|id=A000043}}
|-
|3
|3, 7, 13, 71, 103, 541, 1091, 1367, 1627, 4177, 9011, 9551, 36913, 43063, 49681, 57917, 483611, 877843, ...
|{{OEIS link|id=A028491}}
|-
|4
|2 (Algebra)
|
|-
|5
|3, 7, 11, 13, 47, 127, 149, 181, 619, 929, 3407, 10949, 13241, 13873, 16519, 201359, 396413, ...
|{{OEIS link|id=A004061}}
|-
|6
|2, 3, 7, 29, 71, 127, 271, 509, 1049, 6389, 6883, 10613, 19889, 79987, 608099, ...
|{{OEIS link|id=A004062}}
|-
|7
|5, 13, 131, 149, 1699, 14221, 35201, 126037, 371669, 1264699, ...
|{{OEIS link|id=A004063}}
|-
|8
|3 (Algebra)
|
|-
|9
|None (Algebra)
|
|-
|10
|2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343, ...
|{{OEIS link|id=A004023}}
|-
|11
|17, 19, 73, 139, 907, 1907, 2029, 4801, 5153, 10867, 20161, 293831, ...
|{{OEIS link|id=A005808}}
|-
|12
|2, 3, 5, 19, 97, 109, 317, 353, 701, 9739, 14951, 37573, 46889, ...
|{{OEIS link|id=A004064}}
|-
|13
|5, 7, 137, 283, 883, 991, 1021, 1193, 3671, 18743, 31751, 101089, ...
|{{OEIS link|id=A016054}}
|-
|14
|3, 7, 19, 31, 41, 2687, 19697, 59693, 67421, ...
|{{OEIS link|id=A006032}}
|-
|15
|3, 43, 73, 487, 2579, 8741, 37441, 89009, ...
|{{OEIS link|id=A006033}}
|-
|16
|2 (Algebra)
|
|-
|17
|3, 5, 7, 11, 47, 71, 419, 4799, 35149, 54919, 74509, ...
|{{OEIS link|id=A006034}}
|-
|18
|2, 25667, 28807, 142031, 157051, 180181, ...
|{{OEIS link|id=A133857}}
|-
|19
|19, 31, 47, 59, 61, 107, 337, 1061, 9511, 22051, 209359, ...
|{{OEIS link|id=A006035}}
|-
|20
|3, 11, 17, 1487, 31013, 48859, 61403, ...
|{{OEIS link|id=A127995}}
|-
|21
|3, 11, 17, 43, 271, 156217, 328129, ...
|{{OEIS link|id=A127996}}
|-
|22
|2, 5, 79, 101, 359, 857, 4463, 9029, 27823, ...
|{{OEIS link|id=A127997}}
|-
|23
|5, 3181, 61441, 91943, ...
|{{OEIS link|id=A204940}}
|-
|24
|3, 5, 19, 53, 71, 653, 661, 10343, 49307, ...
|{{OEIS link|id=A127998}}
|-
|25
|None (Algebra)
|
|-
|26
|7, 43, 347, 12421, 12473, 26717, ...
|{{OEIS link|id=A127999}}
|-
|27
|3 (Algebra)
|
|-
|28
|2, 5, 17, 457, 1423, ...
|{{OEIS link|id=A128000}}
|-
|29
|5, 151, 3719, 49211, 77237, ...
|{{OEIS link|id=A181979}}
|-
|30
|2, 5, 11, 163, 569, 1789, 8447, 72871, 78857, 82883, ...
|{{OEIS link|id=A098438}}
|}
 
For more information, see [http://www.primenumbers.net/Henri/us/MersFermus.htm Repunit primes in base −50 to 50], [http://www.fermatquotient.com/PrimSerien/GenRepu Repunit primes in base 2 to 150], [http://www.fermatquotient.com/PrimSerien/GenRepuP Repunit primes in base −150 to −2], and [https://cs.uwaterloo.ca/journals/JIS/VOL3/DUBNER/dubner.pdf Repunit primes in base −200 to −2].
 
=== Algebra factorization of repunit numbers ===
If ''b'' is a [[perfect power]] (can be written as ''m''<sup>''n''</sup>, with ''m'', ''n'' integers, ''n'' > 1) differs from 1, then there is at most one repunit in base ''b''. If ''n'' is a [[prime power]] (can be written as ''p''<sup>''r''</sup>, with ''p'' prime, ''r'' integer, ''p'', ''r'' >0), then all repunit in base ''b'' are not prime aside from ''R<sub>p</sub>'' and ''R<sub>2</sub>''. ''R<sub>p</sub>'' can be either prime or composite, the former examples, ''b'' = -216, -128, 4, 8, 16, 27, 36, 100, 128, 256, etc., the letter examples, ''b'' = -243, -125, -64, -32, -27, -8, 9, 25, 32, 49, 81, 121, 125, 144, 169, 196, 216, 225, 243, 289, etc., and ''R<sub>2</sub>'' can be prime (when ''p'' differs from 2) only if ''b'' is negative, a power of -2, for example, ''b'' = -8, -32, -128, -8192, etc., in fact, the ''R<sub>2</sub>'' can also be composite, for example, ''b'' = -512, -2048, -32768, etc. If ''n'' is not a prime power, then no base ''b'' repunit prime exists, for example, ''b'' = 64, 729 (with ''n'' = 6), ''b'' = 1024 (with ''n'' = 10), and ''b'' = -1 or 0 (with ''n'' any natural number). Another special situation is ''b'' = -4''k''<sup>4</sup>, with ''k'' positive integer, which has the [[aurifeuillean factorization]], for example, ''b'' = -4 (with ''k'' = 1, then ''R<sub>2</sub>'' and ''R<sub>3</sub>'' are primes), and ''b'' = -64, -324, -1024, -2500, -5184, ... (with ''k'' = 2, 3, 4, 5, 6, ..., then no base ''b'' repunit prime exists). It is also conjectured that when ''b'' is neither a perfect power nor -4''k''<sup>4</sup> with ''k'' positive integer, then there are infinity many base ''b'' repunit primes.
 
==History==
Although they were not then known by that name, repunits in base 10 were studied by many mathematicians during the nineteenth century in an effort to work out and predict the cyclic patterns of [[repeating decimal]]s.<ref>Dickson, Leonard Eugene and Cresse, G.H.; ''[[History of the Theory of Numbers]]''; pp. 164-167 ISBN 0-8218-1934-8</ref>
 
It was found very early on that for any prime ''p'' greater than 5, the [[Repeating decimal|period]] of the decimal expansion of 1/''p'' is equal to the length of the smallest repunit number that is divisible by ''p''. Tables of the period of reciprocal of primes up to 60,000 had been published by 1860 and permitted the [[integer factorization|factorization]] by such mathematicians as Reuschle of all repunits up to ''R<sub>16</sub>'' and many larger ones. By 1880, even ''R<sub>17</sub>'' to ''R<sub>36</sub>'' had been factored<ref>Dickson and Cresse, pp. 164-167</ref> and it is curious that, though [[Édouard Lucas]] showed no prime below three million had period [[19 (number)|nineteen]], there was no attempt to test any repunit for primality until early in the twentieth century. The American mathematician [[Oscar Hoppe]] proved ''R<sub>19</sub>'' to be prime in 1916<ref>Francis, Richard L.; "Mathematical Haystacks: Another Look at Repunit Numbers" in The College Mathematics Journal, Vol. 19, No. 3. (May, 1988), pp. 240-246.</ref> and Lehmer and Kraitchik independently found ''R<sub>23</sub>'' to be prime in 1929.
 
Further advances in the study of repunits did not occur until the 1960s, when computers allowed many new factors of repunits to be found and the gaps in earlier tables of prime periods corrected. ''R<sub>317</sub>'' was found to be a [[probable prime]] circa 1966 and was proved prime eleven years later, when ''R<sub>1031</sub>'' was shown to be the only further possible prime repunit with fewer than ten thousand digits. It was proven prime in 1986, but searches for further prime repunits in the following decade consistently failed. However, there was a major side-development in the field of generalized repunits, which produced a large number of new primes and probable primes.


Since 1999, four further probably prime repunits have been found, but it is unlikely that any of them will be proven prime in the foreseeable future because of their huge size.
==References==
 
*{{cite journal
The [[Cunningham project]] endeavours to document the integer factorizations of (among other numbers) the repunits to base 2, 3, 5, 6, 7, 10, 11, and 12.
| last = Bellman | first = Richard | authorlink = Richard Bellman
 
| mr = 0102435
== Demlo numbers ==
| journal = Quarterly of Applied Mathematics
The {{Anchor|Demlo number}} Demlo numbers<ref>{{MathWorld |title= Demlo Number |urlname=DemloNumber}}</ref> 1, 121, 12321, 1234321, ..., 12345678987654321, 1234567900987654321, 123456790120987654321, ..., {{OEIS|id=A002477}} were defined by [[D. R. Kaprekar]] as the squares of the repunits, resolving the uncertainty how to continue beyond the highest digit (9), and named after [[Demlo]] railway station 30 miles from Bombay on the then [[G.I.P. Railway]], where he thought of investigating them.
| pages = 87–90
 
| title = On a routing problem
==See also==
| volume = 16
 
| year = 1958
* [[Repdigit]]
| ref = harv}}.
* [[Recurring decimal]]
*{{cite book|author1-link=L. R. Ford, Jr.|last1=Ford|first1=L. R., Jr.|author2-link=D. R. Fulkerson|last2=Fulkerson|first2=D. R.|title=Flows in Networks|publisher=Princeton University Press|year=1962}}.
* [[All one polynomial]] - Another generalization
*{{Introduction to Algorithms}}, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.1: The Bellman–Ford algorithm, pp.&nbsp;588&ndash;592. Problem 24-1, pp.&nbsp;614&ndash;615.
* [[Goormaghtigh conjecture]]
*{{Introduction to Algorithms}}, Third Edition. MIT Press, 2009. ISBN 978-0-262-53305-8. Section 24.1: The Bellman–Ford algorithm, pp.&nbsp;651&ndash;655.
* [[Wagstaff prime]] - can be thought of as repunit primes with [[negative base]] <math>b=-2</math>
*{{cite book | first1 = George T. | last1 = Heineman | first2 = Gary | last2 = Pollice | first3 = Stanley | last3 = Selkow | title= Algorithms in a Nutshell | publisher=[[O'Reilly Media]] | year=2008 | chapter=Chapter 6: Graph Algorithms | pages = 160–164 | isbn=978-0-596-51624-6 }}
 
*{{cite journal
==Notes==
| last = Yen | first = Jin Y.
{{reflist|2}}
| mr = 0253822
| journal = Quarterly of Applied Mathematics
| pages = 526–530
| title = An algorithm for finding shortest routes from all source nodes to a given destination in general networks
| volume = 27
| year = 1970
| ref = harv}}.


==External links==
==External links==
* [http://snippets.dzone.com/posts/show/4828 C code example]
* [http://code.google.com/p/annas/ Open Source Java Graph package with Bellman-Ford Algorithms]
* [http://www.technical-recipes.com/2012/the-k-shortest-paths-algorithm-in-c/ C++ implementation of Yen's Algorithm (Microsoft Visual Studio project)]


===Web sites===
[[Category:Graph algorithms]]
*{{mathworld|urlname=Repunit|title=Repunit}}
[[Category:Polynomial-time problems]]
*[http://www.cerias.purdue.edu/homes/ssw/cun/third/pmain901 The main tables] of the [http://www.cerias.purdue.edu/homes/ssw/cun/ Cunningham project].
[[Category:Articles with example C code]]
*[http://primes.utm.edu/glossary/page.php?sort=Repunit Repunit] at [http://primes.utm.edu/ The Prime Pages] by [[Chris Caldwell]].
[[Category:Articles with example pseudocode]]
*[http://www.worldofnumbers.com/repunits.htm Repunits and their prime factors] at [http://www.worldofnumbers.com World!Of Numbers].
*[http://www.primes.viner-steward.org/andy/titans.html Prime generalized repunits] of at least 1000 decimal digits by Andy Steward
*[http://www.elektrosoft.it/matematica/repunit/repunit.htm Repunit Primes Project] Giovanni Di Maria's repunit primes page.
*[http://www.primenumbers.net/Henri/us/MersFermus.htm Generalized repunit primes in base -50 to 50]
 
===Books===
*S. Yates, ''Repunits and repetends''. ISBN 0-9608652-0-9.
*A. Beiler, ''Recreations in the theory of numbers''. ISBN 0-486-21096-0. Chapter 11.
*[[Paulo Ribenboim]], ''The New Book Of Prime Number Records''. ISBN 0-387-94457-5.
 
{{Classes of natural numbers}}
{{Prime number classes}}


[[Category:Integers]]
[[ca:Algorisme de Bellman-Ford]]
[[Category:Base-dependent integer sequences]]
[[cs:Bellmanův-Fordův algoritmus]]
[[de:Bellman-Ford-Algorithmus]]
[[es:Algoritmo de Bellman-Ford]]
[[fa:الگوریتم بلمن–فورد]]
[[fr:Algorithme de Bellman-Ford]]
[[ko:벨만-포드 알고리즘]]
[[it:Algoritmo di Bellman-Ford]]
[[he:אלגוריתם בלמן-פורד]]
[[ka:ბელმან-ფორდის ალგორითმი]]
[[lv:Bellmana-Forda algoritms]]
[[nl:Algoritme van Bellman-Ford]]
[[ja:ベルマン-フォード法]]
[[pl:Algorytm Bellmana-Forda]]
[[pt:Algoritmo de Bellman-Ford]]
[[ru:Алгоритм Беллмана — Форда]]
[[th:ขั้นตอนวิธีของเบลแมน-ฟอร์ด]]
[[uk:Алгоритм Беллмана—Форда]]
[[vi:Thuật toán Bellman-Ford]]
[[zh:贝尔曼-福特算法]]

Revision as of 18:39, 10 August 2014

Template:Infobox Algorithm

Template:Tree search algorithm

The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph.[1] For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem. Thus, Bellman–Ford is used primarily for graphs with negative edge weights. The algorithm is named after its developers, Richard Bellman and Lester Ford, Jr.

Negative edge weights are found in various applications of graphs, hence the usefulness of this algorithm.[2] However, if a graph contains a "negative cycle", i.e., a cycle whose edges sum to a negative value, then walks of arbitrarily low weight can be constructed by repeatedly following the cycle, so there may not be a shortest path. In such a case, the Bellman-Ford algorithm can detect negative cycles and report their existence, but it cannot produce a correct "shortest path" answer if a negative cycle is reachable from the source.[3][1]

Algorithm

Bellman–Ford is based on dynamic programming approach. In its basic structure it is similar to Dijkstra's Algorithm, but instead of greedily selecting the minimum-weight node not yet processed to relax, it simply relaxes all the edges, and does this |V | − 1 times, where |V | is the number of vertices in the graph. The repetitions allow minimum distances to propagate accurately throughout the graph, since, in the absence of negative cycles, the shortest path can visit each node at most only once. Unlike the greedy approach, which depends on certain structural assumptions derived from positive weights, this straightforward approach extends to the general case.

Bellman–Ford runs in O(|V|·|E|) time, where |V| and |E| are the number of vertices and edges respectively. 

procedure BellmanFord(list vertices, list edges, vertex source)
   // This implementation takes in a graph, represented as lists of vertices
   // and edges, and modifies the vertices so that their distance and
   // predecessor attributes store the shortest paths.

   // Step 1: initialize graph
   for each vertex v in vertices:
       if v is source then v.distance := 0
       else v.distance := infinity
       v.predecessor := null

   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge uv in edges: // uv is the edge from u to v
           u := uv.source
           v := uv.destination
           if u.distance + uv.weight < v.distance:
               v.distance := u.distance + uv.weight
               v.predecessor := u

   // Step 3: check for negative-weight cycles
   for each edge uv in edges:
       u := uv.source
       v := uv.destination
       if u.distance + uv.weight < v.distance:
           error "Graph contains a negative-weight cycle"

Proof of correctness

The correctness of the algorithm can be shown by induction. The precise statement shown by induction is:

Lemma. After i repetitions of for cycle:

  • If Distance(u) is not infinity, it is equal to the length of some path from s to u;
  • If there is a path from s to u with at most i edges, then Distance(u) is at most the length of the shortest path from s to u with at most i edges.

Proof. For the base case of induction, consider i=0 and the moment before for cycle is executed for the first time. Then, for the source vertex, source.distance = 0, which is correct. For other vertices u, u.distance = infinity, which is also correct because there is no path from source to u with 0 edges.

For the inductive case, we first prove the first part. Consider a moment when a vertex's distance is updated by v.distance := u.distance + uv.weight. By inductive assumption, u.distance is the length of some path from source to u. Then u.distance + uv.weight is the length of the path from source to v that follows the path from source to u and then goes to v.

For the second part, consider the shortest path from source to u with at most i edges. Let v be the last vertex before u on this path. Then, the part of the path from source to v is the shortest path from source to v with at most i-1 edges. By inductive assumption, v.distance after i−1 cycles is at most the length of this path. Therefore, uv.weight + v.distance is at most the length of the path from s to u. In the ith cycle, u.distance gets compared with uv.weight + v.distance, and is set equal to it if uv.weight + v.distance was smaller. Therefore, after i cycles, u.distance is at most the length of the shortest path from source to u that uses at most i edges.

If there are no negative-weight cycles, then every shortest path visits each vertex at most once, so at step 3 no further improvements can be made. Conversely, suppose no improvement can be made. Then for any cycle with vertices v[0], ..., v[k−1],

v[i].distance <= v[(i-1) mod k].distance + v[(i-1) mod k]v[i].weight

Summing around the cycle, the v[i].distance terms and the v[i−1 (mod k)] distance terms cancel, leaving

0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight

I.e., every cycle has nonnegative weight.

Finding negative cycles

When the algorithm is used to find shortest paths, the existence of negative cycles is a problem, preventing the algorithm from finding a correct answer. However, since it terminates upon finding a negative cycle, the Bellman-Ford algorithm can be used for applications in which this is the target to be sought - for example in cycle-cancelling techniques in network flow analysis.[1]

Applications in routing

A distributed variant of the Bellman–Ford algorithm is used in distance-vector routing protocols, for example the Routing Information Protocol (RIP). The algorithm is distributed because it involves a number of nodes (routers) within an Autonomous system, a collection of IP networks typically owned by an ISP. It consists of the following steps:

  1. Each node calculates the distances between itself and all other nodes within the AS and stores this information as a table.
  2. Each node sends its table to all neighboring nodes.
  3. When a node receives distance tables from its neighbors, it calculates the shortest routes to all other nodes and updates its own table to reflect any changes.

The main disadvantages of the Bellman–Ford algorithm in this setting are as follows:

  • It does not scale well.
  • Changes in network topology are not reflected quickly since updates are spread node-by-node.
  • Count to infinity (if link or node failures render a node unreachable from some set of other nodes, those nodes may spend forever gradually increasing their estimates of the distance to it, and in the meantime there may be routing loops).

Yen's improvement

Template:Harvtxt described an improvement to the Bellman–Ford algorithm for a graph without negative-weight cycles. Yen's improvement first assigns some arbitrary linear order on all vertices and then partitions the set of all edges into one of two subsets. The first subset, Ef, contains all edges (vi, vj) such that i < j; the second, Eb, contains edges (vi, vj) such that i > j. Each vertex is visited in the order v1, v2, ..., v|V|, relaxing each outgoing edge from that vertex in Ef. Each vertex is then visited in the order v|V|, v|V|−1, ..., v1, relaxing each outgoing edge from that vertex in Eb. Yen's improvement effectively halves the number of "passes" required for the single-source-shortest-path solution.

Notes

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

References

  • One of the biggest reasons investing in a Singapore new launch is an effective things is as a result of it is doable to be lent massive quantities of money at very low interest rates that you should utilize to purchase it. Then, if property values continue to go up, then you'll get a really high return on funding (ROI). Simply make sure you purchase one of the higher properties, reminiscent of the ones at Fernvale the Riverbank or any Singapore landed property Get Earnings by means of Renting

    In its statement, the singapore property listing - website link, government claimed that the majority citizens buying their first residence won't be hurt by the new measures. Some concessions can even be prolonged to chose teams of consumers, similar to married couples with a minimum of one Singaporean partner who are purchasing their second property so long as they intend to promote their first residential property. Lower the LTV limit on housing loans granted by monetary establishments regulated by MAS from 70% to 60% for property purchasers who are individuals with a number of outstanding housing loans on the time of the brand new housing purchase. Singapore Property Measures - 30 August 2010 The most popular seek for the number of bedrooms in Singapore is 4, followed by 2 and three. Lush Acres EC @ Sengkang

    Discover out more about real estate funding in the area, together with info on international funding incentives and property possession. Many Singaporeans have been investing in property across the causeway in recent years, attracted by comparatively low prices. However, those who need to exit their investments quickly are likely to face significant challenges when trying to sell their property – and could finally be stuck with a property they can't sell. Career improvement programmes, in-house valuation, auctions and administrative help, venture advertising and marketing, skilled talks and traisning are continuously planned for the sales associates to help them obtain better outcomes for his or her shoppers while at Knight Frank Singapore. No change Present Rules

    Extending the tax exemption would help. The exemption, which may be as a lot as $2 million per family, covers individuals who negotiate a principal reduction on their existing mortgage, sell their house short (i.e., for lower than the excellent loans), or take part in a foreclosure course of. An extension of theexemption would seem like a common-sense means to assist stabilize the housing market, but the political turmoil around the fiscal-cliff negotiations means widespread sense could not win out. Home Minority Chief Nancy Pelosi (D-Calif.) believes that the mortgage relief provision will be on the table during the grand-cut price talks, in response to communications director Nadeam Elshami. Buying or promoting of blue mild bulbs is unlawful.

    A vendor's stamp duty has been launched on industrial property for the primary time, at rates ranging from 5 per cent to 15 per cent. The Authorities might be trying to reassure the market that they aren't in opposition to foreigners and PRs investing in Singapore's property market. They imposed these measures because of extenuating components available in the market." The sale of new dual-key EC models will even be restricted to multi-generational households only. The models have two separate entrances, permitting grandparents, for example, to dwell separately. The vendor's stamp obligation takes effect right this moment and applies to industrial property and plots which might be offered inside three years of the date of buy. JLL named Best Performing Property Brand for second year running

    The data offered is for normal info purposes only and isn't supposed to be personalised investment or monetary advice. Motley Fool Singapore contributor Stanley Lim would not personal shares in any corporations talked about. Singapore private home costs increased by 1.eight% within the fourth quarter of 2012, up from 0.6% within the earlier quarter. Resale prices of government-built HDB residences which are usually bought by Singaporeans, elevated by 2.5%, quarter on quarter, the quickest acquire in five quarters. And industrial property, prices are actually double the levels of three years ago. No withholding tax in the event you sell your property. All your local information regarding vital HDB policies, condominium launches, land growth, commercial property and more

    There are various methods to go about discovering the precise property. Some local newspapers (together with the Straits Instances ) have categorised property sections and many local property brokers have websites. Now there are some specifics to consider when buying a 'new launch' rental. Intended use of the unit Every sale begins with 10 p.c low cost for finish of season sale; changes to 20 % discount storewide; follows by additional reduction of fiftyand ends with last discount of 70 % or extra. Typically there is even a warehouse sale or transferring out sale with huge mark-down of costs for stock clearance. Deborah Regulation from Expat Realtor shares her property market update, plus prime rental residences and houses at the moment available to lease Esparina EC @ Sengkang.
  • 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

    My blog: http://www.primaboinca.com/view_profile.php?userid=5889534.
  • Template:Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.1: The Bellman–Ford algorithm, pp. 588–592. Problem 24-1, pp. 614–615.
  • Template:Introduction to Algorithms, Third Edition. MIT Press, 2009. ISBN 978-0-262-53305-8. Section 24.1: The Bellman–Ford algorithm, pp. 651–655.
  • 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

    My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
  • One of the biggest reasons investing in a Singapore new launch is an effective things is as a result of it is doable to be lent massive quantities of money at very low interest rates that you should utilize to purchase it. Then, if property values continue to go up, then you'll get a really high return on funding (ROI). Simply make sure you purchase one of the higher properties, reminiscent of the ones at Fernvale the Riverbank or any Singapore landed property Get Earnings by means of Renting

    In its statement, the singapore property listing - website link, government claimed that the majority citizens buying their first residence won't be hurt by the new measures. Some concessions can even be prolonged to chose teams of consumers, similar to married couples with a minimum of one Singaporean partner who are purchasing their second property so long as they intend to promote their first residential property. Lower the LTV limit on housing loans granted by monetary establishments regulated by MAS from 70% to 60% for property purchasers who are individuals with a number of outstanding housing loans on the time of the brand new housing purchase. Singapore Property Measures - 30 August 2010 The most popular seek for the number of bedrooms in Singapore is 4, followed by 2 and three. Lush Acres EC @ Sengkang

    Discover out more about real estate funding in the area, together with info on international funding incentives and property possession. Many Singaporeans have been investing in property across the causeway in recent years, attracted by comparatively low prices. However, those who need to exit their investments quickly are likely to face significant challenges when trying to sell their property – and could finally be stuck with a property they can't sell. Career improvement programmes, in-house valuation, auctions and administrative help, venture advertising and marketing, skilled talks and traisning are continuously planned for the sales associates to help them obtain better outcomes for his or her shoppers while at Knight Frank Singapore. No change Present Rules

    Extending the tax exemption would help. The exemption, which may be as a lot as $2 million per family, covers individuals who negotiate a principal reduction on their existing mortgage, sell their house short (i.e., for lower than the excellent loans), or take part in a foreclosure course of. An extension of theexemption would seem like a common-sense means to assist stabilize the housing market, but the political turmoil around the fiscal-cliff negotiations means widespread sense could not win out. Home Minority Chief Nancy Pelosi (D-Calif.) believes that the mortgage relief provision will be on the table during the grand-cut price talks, in response to communications director Nadeam Elshami. Buying or promoting of blue mild bulbs is unlawful.

    A vendor's stamp duty has been launched on industrial property for the primary time, at rates ranging from 5 per cent to 15 per cent. The Authorities might be trying to reassure the market that they aren't in opposition to foreigners and PRs investing in Singapore's property market. They imposed these measures because of extenuating components available in the market." The sale of new dual-key EC models will even be restricted to multi-generational households only. The models have two separate entrances, permitting grandparents, for example, to dwell separately. The vendor's stamp obligation takes effect right this moment and applies to industrial property and plots which might be offered inside three years of the date of buy. JLL named Best Performing Property Brand for second year running

    The data offered is for normal info purposes only and isn't supposed to be personalised investment or monetary advice. Motley Fool Singapore contributor Stanley Lim would not personal shares in any corporations talked about. Singapore private home costs increased by 1.eight% within the fourth quarter of 2012, up from 0.6% within the earlier quarter. Resale prices of government-built HDB residences which are usually bought by Singaporeans, elevated by 2.5%, quarter on quarter, the quickest acquire in five quarters. And industrial property, prices are actually double the levels of three years ago. No withholding tax in the event you sell your property. All your local information regarding vital HDB policies, condominium launches, land growth, commercial property and more

    There are various methods to go about discovering the precise property. Some local newspapers (together with the Straits Instances ) have categorised property sections and many local property brokers have websites. Now there are some specifics to consider when buying a 'new launch' rental. Intended use of the unit Every sale begins with 10 p.c low cost for finish of season sale; changes to 20 % discount storewide; follows by additional reduction of fiftyand ends with last discount of 70 % or extra. Typically there is even a warehouse sale or transferring out sale with huge mark-down of costs for stock clearance. Deborah Regulation from Expat Realtor shares her property market update, plus prime rental residences and houses at the moment available to lease Esparina EC @ Sengkang.

External links

ca:Algorisme de Bellman-Ford cs:Bellmanův-Fordův algoritmus de:Bellman-Ford-Algorithmus es:Algoritmo de Bellman-Ford fa:الگوریتم بلمن–فورد fr:Algorithme de Bellman-Ford ko:벨만-포드 알고리즘 it:Algoritmo di Bellman-Ford he:אלגוריתם בלמן-פורד ka:ბელმან-ფორდის ალგორითმი lv:Bellmana-Forda algoritms nl:Algoritme van Bellman-Ford ja:ベルマン-フォード法 pl:Algorytm Bellmana-Forda pt:Algoritmo de Bellman-Ford ru:Алгоритм Беллмана — Форда th:ขั้นตอนวิธีของเบลแมน-ฟอร์ด uk:Алгоритм Беллмана—Форда vi:Thuật toán Bellman-Ford zh:贝尔曼-福特算法

  1. ↑ 1.0 1.1 1.2 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

    My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
  2. ↑ 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

    My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
  3. ↑ Kleinberg, Jon; Tardos, Éva (2006), Algorithm Design, New York: Pearson Education, Inc..
Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=39099"